stack item FIFO or LIFO to minimise page miss

[albertnetymk]

https://github.com/sustrik/libmill/blob/master/stack.c#L77-L78 This makes sense, because next pop would get the stack item from previous push, which is presumably "hot". However, https://github.com/sustrik/libmill/blob/master/stack.c#L76 mentions FIFO, while it seems like LIFO. The implementation, https://github.com/sustrik/libmill/blob/master/stack.c#L169 if I understand correctly, is FIFO actually. Is the comment outdated or what?

[sustrik]

It's LIFO, of course. Comment fixed. Thanks for spotting it!

[albertnetymk]

The code https://github.com/sustrik/libmill/blob/master/stack.c#L169 calls "push_back", which places item in the end, doesn't it?

[sustrik]

Ah, correct. Look few lines below that. The stack is popped and deallocated. However, we cannot deallocate the stack we are running on... I guess that with a bit of effort you can reshuffle the code is such a way that it's true LIFO.

[albertnetymk]

You meat this one: https://github.com/sustrik/libmill/blob/master/stack.c#L178?

Since it's LIFO, could we do sth like "pop_back" to free the last in the slist?

[sustrik]

I would simply first delete one stack from the cache (if appropriate) then put the current one to the cache.

[albertnetymk]

The stack that needs to be deleted should be the last one, if LIFO is respected. Had a quick look at slist, it seems that it doesn't support implementing pop_back easily...

Since each stack frame has the same size, using sth like slab allocator seems more sensible, IMO.

[sustrik]

Sounds good, would you like to implement that?

[albertnetymk]

Further investigation convinced me that ring buffer is a simple data structure for LIFO in this case.