std::vector<> considered harmful

[lucasart]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search.

Exactly!

A well written chess engine should not do any dynamic memory allocation, apart from the obvious hash table(s).

If you need to dynamically allocate/resize anything, you're doing it all wrong. Instead of wondering whether to choose std::vector vs. pointer+realloc, ask yourslef what you are doing wrong and redesign your code.

[Henk]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search.

Exactly!

A well written chess engine should not do any dynamic memory allocation, apart from the obvious hash table(s).

If you need to dynamically allocate/resize anything, you're doing it all wrong. Instead of wondering whether to choose std::vector vs. pointer+realloc, ask yourslef what you are doing wrong and redesign your code.

I am currently using movelists but also iterator objects and move handlers one for captures, one for killers etc. All dynamically allocated. Lots of work to do.

If I am going to reuse movelists of a pre-allocated pool it might be that clearing them will be expensive too. But of course instead of allocating power(N, BF) movelists I only need to allocate N such lists but they still have to be cleared power(N, ..) times.

[flok]

If you need to dynamically allocate/resize anything, you're doing it all wrong. Instead of wondering whether to choose std::vector vs. pointer+realloc, ask yourslef what you are doing wrong and redesign your code.

Measurements tell me differently.
Malloc and friends use less than 0.1% of the total in my program.

[mvk]

Measurements tell me differently.
Malloc and friends use less than 0.1% of the total in my program.

I have malloc/realloc/free in my input processor, in the initialisation of the evaluation patterns, in some PV nodes and in all split nodes. Wrapped in my List() macros, there is a common theme here... No performance impact and no need to be dogmatic about it. (But a bad idea in regular nodes).

[lucasart]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search.

Exactly!

A well written chess engine should not do any dynamic memory allocation, apart from the obvious hash table(s).

If you need to dynamically allocate/resize anything, you're doing it all wrong. Instead of wondering whether to choose std::vector vs. pointer+realloc, ask yourslef what you are doing wrong and redesign your code.

I am currently using movelists but also iterator objects and move handlers one for captures, one for killers etc. All dynamically allocated. Lots of work to do.

If I am going to reuse movelists of a pre-allocated pool it might be that clearing them will be expensive too. But of course instead of allocating power(N, BF) movelists I only need to allocate N such lists but they still have to be cleared power(N, ..) times.

I said well written engine. Obviously that excludes any work from: you, Folkert, Syed, etc.

[sje]

On dynamic storage allocation

Both Oscar and Symbolic use dynamic storage allocation for many purposes, and this feature helps with the goal of avoiding fixed limits on search depth, game length, etc. The difference between the two programs is that Oscar has its own heap while Symbolic uses a heap controlled by C++ library routines.

Oscar and Symbolic dynamically allocate memory only when necessary and recycle the memory using their own routines whenever possible. The result is that beyond a small fraction of a second after program start-up, the library/system overhead for dynamic allocation is far too small to be measurable; it's something like O(log log N). When the program shuts down, there is also a very small library/system overhead where the program gracefully releases all of its dynamically allocated objects, because Oscar and Symbolic are good boys and play nicely with others.

Recycling is done among dynamically allocated nodes of the same type. Each node has prev/next pointers, and each node belongs to a list which has head/tail pointers. A node is recycled by detaching it from one list (usually at the tail) and attaching it to second list (also, usually at the tail). Simple stuff; easy with C++ templates, a bit more verbose with regular C code.

Were you around in the mid 1970s? There was a popular dance called "The Bump" where two dancers would bump tails to exchange momentum. It's the same thing with Oscar and Symbolic; the tails of two lists are bumped to transfer an allocated node.

Code: Select all

  // Save the move

  if (positionptr->freemovelistptr->count == 0)
    MoveListAppendNode(positionptr->freemovelistptr, MoveNodeNew());
  MoveNode * const movenodeptr = MoveListDetachTail(positionptr->freemovelistptr);
  movenodeptr->move = move;
  MoveListAppendNode(positionptr->usedmovelistptr, movenodeptr);

[flok]

I said well written engine. Obviously that excludes any work from: you, Folkert, Syed, etc.

Always nice if the authority in this field shares infinite wisdom.

[Henk]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search.

Exactly!

A well written chess engine should not do any dynamic memory allocation, apart from the obvious hash table(s).

If you need to dynamically allocate/resize anything, you're doing it all wrong. Instead of wondering whether to choose std::vector vs. pointer+realloc, ask yourslef what you are doing wrong and redesign your code.

I am currently using movelists but also iterator objects and move handlers one for captures, one for killers etc. All dynamically allocated. Lots of work to do.

If I am going to reuse movelists of a pre-allocated pool it might be that clearing them will be expensive too. But of course instead of allocating power(N, BF) movelists I only need to allocate N such lists but they still have to be cleared power(N, ..) times.

I said well written engine. Obviously that excludes any work from: you, Folkert, Syed, etc.

Ok that's a good reason for me to quit.

[vittyvirus]

In Chesser, perft(5) with vector:
1231 ms
without vector:
484 ms

[vittyvirus]

I wonder if any of you has suggestions for improving it any further.

Do not allocate any objects at all within your search.

Exactly!

A well written chess engine should not do any dynamic memory allocation, apart from the obvious hash table(s).

If you need to dynamically allocate/resize anything, you're doing it all wrong. Instead of wondering whether to choose std::vector vs. pointer+realloc, ask yourslef what you are doing wrong and redesign your code.

I am currently using movelists but also iterator objects and move handlers one for captures, one for killers etc. All dynamically allocated. Lots of work to do.

If I am going to reuse movelists of a pre-allocated pool it might be that clearing them will be expensive too. But of course instead of allocating power(N, BF) movelists I only need to allocate N such lists but they still have to be cleared power(N, ..) times.

I said well written engine. Obviously that excludes any work from: you, Folkert, Syed, etc.

Ok that's a good reason for me to quit.

Depends on what Lucas means by a 'well written engine'. He wrote a 2800 and now thinks himself god.