Implementing pool allocator

[ampli]

In #673 I implemented a pool allocator in the exprune code.
The idea was to malloc big chunks of memory and then sub-allocate each element from these chunks.
This prevents absolutely most of the overhead of malloc/free. It also allows zeroing (if needed) of the whole pool at once instead of each element separately. This particular pool is reused in each pruning round, but this is not needed for a general use.
The disjunct/connector packing also use a kind of pool allocator.

My proposal is to implement this idea in a general way, by a simple pool allocator.
(The pools are to be freed after handling each sentence, at least for now - this can be changed if desired.)

Proposed API (pool_alloc.c, pool_alloc.h):

typedef struct memory_pool_chain_s memory_pool_chain;
struct memory_pool_chain_s
{
	memory_pool_chain *next;
	char block[];
};

typedef struct
{
	memory_pool_chain *chain;
	void *alloc_curr;
	size_t block_size;
	size_t element_size;
} memory_pool;

// Create a memory pool with the given attributes.
// Each pool block contains (num_elements*element_size) bytes.
memory_pool *mp = pool_init(size_t num_elements,  size_t element_size, bool zero_out)

// Destroy the given pool.
void pool_destroy(memory_pool *mp)

// Allocate an element from the given pool.
// A new pool block is internally allocated if needed.
void *pool_alloc(memory_pool *mp)

// (Maybe latter.)
// Free the given element from the given pool
void *pool_free(memory_pool *mp, void *element)

// Prepare the given pool for reusing:
// Zero it out if needed, set the sub-allocation to be from its start.
void *pool_reuse(memory_pool *mp)

My current implementation about is 30 lines of code, but I guess some more will added.
Using such pools makes it more tricky to free all sentence memory in case memory is exhausted (a planned work), but it is "easily" possible too.

[linas]

Pools make me nervous. There is a long history of people trying to improve on malloc, only to have things blow up (ie. got slower, leak memory, be buggy). There are several memory-pool malloc-replacement/add-on libraries out there, they might be worth playing with. But you can try this, I guess -- just be careful with limiting complexity...

[ampli]

My implementation is not too different than this.
It has some small added features like added arguments in the pool creation (BTW, I will rename my pool_init() to pool_create()), and no need to mention the element size when allocating an element (pool_alloc()).

[linas]

Yeah, OK, that seems both harmless and likely to improve performance.

[ampli]

I finished the memory pool implementation and got these speedups:

file/sentence	speedup
en/corpus-fixes.batch	10%
en/corpus-basic.batch	6%
ru/corpus-basic.batch	3%
The problem is ...	10.5%
The Russian sentence from #537	8%

The only place I used it in the dictionary read handling is to allocate the connector descriptor elements (condesc_t). I guess that using it for allocation Dict_node may improve read performance.

There are more places in which it can be used, e.g. building disjunct, postprocessing, linkage extracting.
I also have a very old branch that introduced a specially tailored memory pool to string_set, but the results were disappointing (only a little saving) but now I know better so I may try it again.

In exprune.c I have left the specially tailored memory pool I recently introduced because it performs somewhat better than my general purpose implementation and has a small enough code.

In sentence_delete(), the memory pools are freed. The memory pools for the fast matcher and the count memoization are reused if parsing with null_count>0 is done.

Memory pools have a drawback that element memory overflow cannot be found with ASAN, and they need a special valgrind support incorporated into them in order that valgrind will be able to make memory checks on them (and I didn't implement that). To solve this drawback, I also wrote a "fake memory pool" support, that just uses "malloc()" for each element, and it is used if the library is compiled with CFLAGS=-DPOOL_ALLOCATOR=0.

If these savings seem fine for introducing such an infrastructure, I will polish it some more and send a PR.

[linas]

Sure. The above-mentioned design seemed reasonable, and the speedups are worthwhile.