[Jenya_]

On my work we do use linked lists, they are simple and convenient to collect a few items of data together when the item count is not known in advance. The trick is to allocate linked list structures from the arena allocator (which keeps these structures close in memory). The programs in my work may run for days and may use terabytes of RAM (EDA chip design verification).

I agree that linked lists could be optimized, but usually they are not the worst offender. The biggest gains in performance usually happen when an accidental O(n^2) slowdown is replaced with a correct n*log(n) version.

[CyberDildonics]

There are a couple of large red flags here, but why not just use an array instead of an arena allocator and a linked list (of pointers I'm guessing).

If you need a linked list, use an array with indices and you can cut the size in half if you don't need 64 bit integers. If it has to be enormous, make a linked list of arrays for better locality.

[Jenya_]

Our arena allocator does not reuse memory for simplicity (it allocates only forward, like a stack). A lot of the libc malloc complexity comes from the need to manage deallocated pieces of memory.

Which means that using array over this arena would waste more memory (due to array resizing) than linked list. When array is resized, the unused memory from the old array will stay unused until the whole arena is deallocated.

[CyberDildonics]

> Which means that using array over this arena would waste more memory (due to array resizing) than linked list

I think you are way off track. The point here is that whatever you are doing is unnecessary. You don't need an arena and probably don't need a linked list. You are using an arena allocator as an array already if you are never freeing anything. Just make fewer large allocations.

> does not reuse memory for simplicity (it allocates only forward, like a stack)

First, stacks can shrink when items are popped off. Second, if you are using an 'arena allocator' and a linked list on top of it when you could actually just allocate memory into an array are you really gaining simplicity? You are purposely not reusing memory and have a program using terabytes of memory and running for multiple days. Is that really simplicity?

Pretty much everything you have said so far is an enormous red flag, but the good news is that there are probably ways where you can use orders of magnitude less time and memory while making the program more straight forward.

[Jenya_]

The problem solved by arena allocators here is to avoid many calls to malloc. System allocator is slow, especially in multithreaded environment. Instead of calling malloc 1000 times to allocate 1000 small pieces (like 16 bytes sized each), malloc is called once and then all the small pieces are carved from the big memory block.

The arena allocators are also popular in game development. Memory is allocated from the arena allocator during frame processing (16 ms), and all this allocated memory is deallocated at once at the end of the frame.

[CyberDildonics]

Again, I don't understand why you wouldn't just allocate large arrays, especially knowing that excessive memory allocation is slow and going to lock on top of that (you could use jemalloc, but that is orthogonal here).

> Instead of calling malloc 1000 times to allocate 1000 small pieces (like 16 bytes sized each), malloc is called once and then all the small pieces are carved from the big memory block.

No one who has any idea about performance is saying lots of memory allocations are ok. It sounds like what you are doing though is allocating arrays but then using them for 'arena allocators' when you could just use them directly and use indices for ordering if you need that.

> The arena allocators are also popular in game development. Memory is allocated from the arena allocator during frame processing (16 ms), and all this allocated memory is deallocated at once at the end of the frame.

I would ask why the memory needs to be deallocated at the end of each frame. A C++ vector can be cleared without releasing its capacity. What you really want is to have all the memory that you need allocated once so it can be reused over and over easily. There is no reason to involve an allocator on a frame to frame basis of a video game unless you go over what you already thought you would need.

If you have 'millions' of 'memory managers', why not just use a few big arrays? It really seems like an over complication of a problem that doesn't need to be difficult. I'm surprised no one would take the time to clean that out if there are terabytes of memory used and multiple days for single program runs.

[Jenya_]

Lol, so many questions :). I myself only use linked list when I do not know in advance how many items I will get. Otherwise I do allocate an array.

[Jenya_]

Yes, it works fine. I will only add that we do reuse memory. The program deallocates memory managers when they are no longer needed (there could be millions of them at any single time).