C programming question

[lucasart]

I have a board structure that looks like:

Code: Select all

struct board {
	// some stuff
	struct undo_info *begin, *end, *ui;
};

'some stuff' basically contains everything that is going to be recomputed dynamically upon playing and undoing moves. In contrast, some information either cannot be recomputed on undo, or it would be a waste of performance to do so. This information is what I put in 'struct undo_info'.

The triplet (begin, end, ui) represent an undo stack: it's a dynamic array that starts at 'begin', ends at 'end' (not included) and whose current position (ie. stack top) is 'ui'.

C is a Spartan language, in which the programmer needs to take care of memory allocation, reallocation, and freeing himself. What is the standard strategy to deal with such problems? Here's the simplest strategy I can think of:

1/ when I call clear_board(), I allocate (let's say) 16 elements:

Code: Select all

begin = calloc(sizeof(undo_info), 16);

2/ when I call play(), to play a move on the board, I need to start by adding a new element undo_info on top of the stack, copy the current one's content into it. Of course, this can lead to ui >= end, in which case, I need to call realloc(), to grow the stack by another 16 elements:

Code: Select all

if (ui+1 >= end)
    begin = realloc(begin, sizeof(undo_info) * (end - begin + 16));

The problem with that strategy is that the burden of freeing memory now belongs to the foreign code. And in rather subtile ways. Example of such foreign code that could leak:

Code: Select all

struct board b;
set_pos(&b, "2r1qn2/2P2pk1/2RQ2p1/4P2p/1R5P/P7/7P/K7 w - - 5 64 ");

Now play/undo some moves (what a typical search would do). note that the undo_info buffer will grow but never shrink. This is a good thing (lazy reallocation).
Calling set_pos() again will call clear_bord(), which will inevitably leak. The point is that clear_board() cannot start by freeing the buffer, because it cannot know if the pointer contains garbage or a valid adress that needs to be freed. Also, a more economical strategy would be to not free but reuse the already allocated buffer.

Code: Select all

// Memory leak!
set_pos(&b, "2r1qn2/2P2pk1/2RQ2p1/4P2p/1R5P/P7/7P/K7 w - - 5 64 ");

In this scheme, the correct solution would be to free the buffer in the foreign code, before the second call to set_pos(), which is ugly because the foreign code should not have to know about such ugly details.

What strategy would you recommend ?

PS: Please don't lecture me about the benefits of C++ and STL/Boost etc. This is a C question.

[lucasart]

Sorry for that. I think I found the answer to my question, by looking more deeply into the realloc() documentation. realloc() resolves this problem by itself. The only constraint is that the pointer should always be NULL or valid. It must never contain any garbage. So, only zeroing the pointer (first time a struct board is declared) belong in the foreign code. After than calling realloc() several times is ok. I basically need to use realloc everywhere, and never malloc/calloc here.

[Michel Van den Bergh]

This is a relatively common design pattern in C.

pointer!=NULL => pointer valid

(for allocated pointers).

If you want to reuse a non NULL pointer, free it first (e.g. implicitly as in realloc). The contract says that the free is automatically legal.

This allows you to do primitive object oriented programming in C. It works fine as long as there are not several pointers,
pointing to the same data.

[lucasart]

What bothers me with all this is that, no matter how you do it, there is always some intelligence that the foreign code needs to have. In C++ a constructor/destructor would resolve the problem. Let's take a simple example: suppose we want to build a 'stack of int' structure, with automatically growing buffer

Code: Select all

struct stack {
    int *begin, *end, *top;
};

void push(struct stack *s, int x) {
    if (s->top+1 >= s->end) {
        s->begin = realloc(s->begin, sizeof(int) * (s->end - s->begin + ALLOC_BY));
        assert(s->begin);
    }
    *++s->top = x;
}

int pop(struct stack *s) {
    assert(s->top >= s->begin);
    return *s->top--;
}

stack_constructor(struct stack *s) {
    s->begin = s->top = s->end = NULL;
}

stack_destructor(struct stack *s) {
    free(s->begin);
    s->begin = s->top = s->end = NULL;
}

Now let's see what foreign code using this stack would look like:

Code: Select all

    struct stack s;
    stack_constructor(&s);  // UGLY !

    // stack up 10 values
    for (int i = 0; i < 10; push(&s, i++));

    // pop() until nothing left
    while (s.top >= s.begin)
        printf("pop: %d\n", pop(&s));

    stack_destructor(&s);    // UGLY !

Here you see that the foreign code is responsible for:
* establishing the contract: here by calling stack_constructor().
* freeing the memory: here by calling stack_destructor().

I was just wondering if there is not a better way to avoid this problem. It seems there is not, and it's inherent to C programming. Still, even with the annoyances, I prefer to program a chess engine in C than in C++. If only we could have only the good stuff in C++ without all the crap.

[User923005]

I was just wondering if there is not a better way to avoid this problem. It seems there is not, and it's inherent to C programming. Still, even with the annoyances, I prefer to program a chess engine in C than in C++. If only we could have only the good stuff in C++ without all the crap.

You can.
There are a few subtle differences between C and C++, but you can write procedural C++ code that compiles as C or C++ and the efficiency will be about the same.
It's a fairly common practice, especially for people who are fluent in C and fairly new to C++.

[syzygy]

What strategy would you recommend ?

Just allocate the undo stack once and make it big enough.

Still, even with the annoyances, I prefer to program a chess engine in C than in C++. If only we could have only the good stuff in C++ without all the crap.

It is the programmer that decides to use the "crap".

[hyatt]

I have seen multiple C++ chess engines over the years that were uncluttered, without templates, all the dynamic allocation nonsense and such. Using such stuff is a choice, one that is not forced on anyone by the language. You can write bad code directly in C, in fact. I've seen more than one that does zillions of malloc() calls which is nuts.

[lauriet]

Well guys, the answer is staring you right in the face.
Switch to PASCAL. Then you can program in a simple, logical, transparent, self documenting, easy to understand,
pleasure to use language. Then you would not need to ask questions about how it works.

Regards
Laurie

[lucasart]

Well guys, the answer is staring you right in the face.
Switch to PASCAL. Then you can program in a simple, logical, transparent, self documenting, easy to understand,
pleasure to use language. Then you would not need to ask questions about how it works.

Regards
Laurie

I've learnt Pascal a while ago, and loved it back then. It used to be my favorite language back then... until I learnt C. The simplicity, power, and beauty of C will never stop amazing me, even today, more than 40 years after its conception. Denis Ritchie was truly a genious, especially when you consider C to the programming languages that were available in the early 70s (COBOL, FORTRAN, BASIC, etc. all of which are total and utter crap in comparison to C).

Basically:

• Pascal is easier for beginners than C. Consequently it is much easier than C++ (that's not hard considering how horribly complicated and poorly designed C++ is:
  yosefk.com/c++fqa/defective.html‎
• For competent programmers, not afraid by the low-level aspects of C, C beats the pants off Pascal on anything that really matters in real application developpement (as opposed to academic toys). The prophet Brian Kerninghan explains why, in great details, in this link:
  http://www.lysator.liu.se/c/bwk-on-pascal.html
• C compilers are much better than Pascal ones: http://www.talkchess.com/forum/viewtopic.php?t=29562. So, if performance is an important issue (as is the case for chess programming), Pascal is not an option. Btw, if performance is not an issue, I would rather use a real high level and modern programming language like Python, rather than a dinosaure like Pascal.

Conclusion: Pascal is not good for anything, except perhaps for being an academic toy that may be good at teaching structured programming to beginners. And even in that case, I think it's much preferable to teach beginners a real high level language like Python, that can actually solve real life problems efficiently.

[User923005]

Pascal compilers are a little behind C and C++ compilers, but the free pascal compiler from the CodeTyphon project is pretty good:
http://www.pilotlogic.com/sitejoom/index.php/codetyphon

I think that the real answer is to choose the language you are most familiar with. If you are a Java expert, make a Java program. If you are a Pascal expert, make a Pascal program. If you are a Fortran expert, make a Fortran program. You can compile the Java to native binaries. Yes, the Java, Pascal and Fortran will be a little slower than C and C++. But the algorithms chosen are orders of magnitude more important than the compiler chosen.

If you want the last little molecule of speed, you might have to learn C or C++, but most chess programmers are hobby programmers anyway and are not going to beat the top ten programs in the world anyway.

I have seen beautiful COBOL (no, really) and atrocious C. The beauty in programming comes from the programmer (OK, the language can help a little).