After using an std vector to hold my move list for my chess engine, I realised that because chess has an averaging factor of 35 (i.e. something like 35 legal moves from a typical position), the vector was resizing a lot, thereby negatively impacting the performance of the move generator. One way around this (which I only realised today) is by reserving a minimum capacity for the vector. However, the possibility of using alloca() attracted my attention. This is probably a very simple question, but the documentation on alloca() is pretty scarce, with very very few examples of how to use it.
So an answer from Allocation of variable-sized class mentions that stack allocations cannot be resized. Nevertheless, would the following be valid?
struct MoveList
{
MoveList(): capacity(10)
{
moves = (Move*) alloca(sizeof(Move) * 10);
}
void resize()
{
capacity *= 2;
moves = (Move*) alloca(sizeof(Move) * capacity );
}
void push_back();
Move* moves;
int size;
int capacity;
}
Specifically, if say, a capacity of 10 is insufficient from alloca() the first time around, is it syntactically valid (and correct) to simply call alloca() again to allocate some more memory? Will this method give better performance (compared to std vector with reserve()), or only increase the chance of a stack overflow? My Move struct requires some 28 bytes of memory, and I suspect that the engine will recursively search (using alpha-beta) to maybe 7 or 8 ply maximum so that perhaps some 28 * 35 * 8 ~ 8kb max will be used from the stack. I read somewhere that typically stacks have a limit of 1Mb so this should not be too much right?
Edit: Thanks to the answers below, I realise now that my initial understanding of what alloca() did was wrong. However, I would still like to know if it is possible to use alloca() in the manner below:
int main()
{
int* arr = (int) alloca(sizeof(int));
arr = alloca(sizeof(int) * 2 ));//is this 'resizing' valid?
}
The function alloca
allocates memory on the stack, and the memory is no longer available as soon as the function in which alloca
was called returns. It means that as soon as MoveList
constructor or resize
function returns, the memory is no longer available. Your assumption that somehow you will be able to use this memory during lifetime of MoveList
object is wrong.
The best option for you is to use std::vector
and reserve.