Eg I allocate dynamic array in arena with initial size 1 byte. I insert value with size of 2 byte into it. There is no enough allocation, so the arena grow by allocating new block, now the arena becomes
[1 byte]–chain–[2 byte]
The dynamic array copy old data to the new block and point to the new block. Will the previous 1 byte is freed? Or it is still there as garbage memory?
As I understood it, it is garbage memory (i.e. it is not freed and handed back to the OS), until the arena is .deinit()-ed. The memory could be reused at some other pointed by the arena derived allocator, but as @invlpg pointed out it doesn’t do so (except for when you would free the latest alloced space, which you don’t).
This is slightly misleading. The arena allocator as it is, will not do that.
You’re probabl right, I haven’t line by line examined the arena code
I interpreted the comment (in ArenaAllocator.zig) that it does:
// We need a new node! First, we search `free_list` for one that's big
// enough, if we don't find one there we fall back to allocating a new
// node with `child_allocator` (if we haven't already done that!).
but looking at the free() call it is clear it only doesn’t keep a free list for re-use and only does something special if you free the element that was last allocated.
The free list is only used when two threads are racing to insert a new node into the used list. Both threads have to optimistically allocate a new node first (otherwise there would be nothing they could try to insert) and one of them will win the race eventually, at which point the other thread is stuck with a leftover node. Instead of freeing the unused node with the child allocator, the losing thread inserts it into the free list to reuse it at a later point in time. This potentially saves a future alloc call to the backing allocator. It also avoids wasting memory when e.g. one arena is backed by another one, as freeing the leftover node would probably be a noop in that case.