Octacone wrote:
You really couldn't resist replying to this thing, couldn't you? As if you had a detector that could sniff when I mention bitmaps.
I couldn't, and I've been away for a few days, so...
The main reason was that I really consider bitmap to be a tiny bit more complex than a stack.
Octacone wrote:
This is based of my personal experience, to me I can wrap my head around it more easily that I can with a stack.
You're of course free to use whatever you like, but I do think that wrapping your head around a stack should be fairly trivial.
Octacone wrote:
Also there was an old topic speaking about how bad the stack was. I think it had something to do with DMA pages + not being space efficient.
Not sure which thread, and not sure what the comparison was. Assuming the simple case of only allocating a single 4KiB physical page frame stack is probably the fastest and best performing option there is.
If you need to handle special memory ranges (for example for DMA), then things get slightly more complex. A simple solution is to have two (or more) stacks, where the low memory is put in the special DMA stack and rest goes to the normal stack.
A bitmap needs to search the bitmap for a free page, a stack just pops it. To get even remotely decent performance from bitmap you need to "remember" where you last looked in the bitmap so you can start the next search there, instead of the beginning (where all memory is likely to be in use), but even that isn't very good, which means the complexity keeps rising to get better performance.
Octacone wrote:
When it comes to allocation performance, I really don't care about 2.000001 ms more or less. "User doesn't care about things their eye can't notice."
Not sure what you are saying here, I'm guessing you're trying to say that the difference between stack and bitmap is on the order of 0.000001, or in other words 1ns? The difference between a simple stack vs a simple bitmap in non-pathological cases would be massively bigger than 1ns.
I'm not accounting for the syscall overhead, just the bitmap vs stack algorithm. Best case scenario (the bitmap "pointer" points to free bit) would likely give very close performance to stack and everything else increasingly worse. On average I'd expect 2x to 1000x worse performance. I don't have any tests to provide more useful numbers.
Octacone wrote:
It is very easy to implement a bitmap based allocator, there are plethora of examples and other documents that can get you started, while you can't say that for your stack.
Looks like both of our opinions are very subjective and that the author should decided himself/herself what he/she thinks is the best.
When a page is allocated you return the current "stack pointer", it points to a free page. Before returning it you read from that page what is the next "stack pointer" and that gets stored in the "stack pointer" for next time. This way the stack uses the free pages themselves, thus the stack itself only needs memory for a couple of variables, so effectively it uses no memory at all.
When you deallocate (free) a page you do the reverse, you write to the newly free page the current "stack pointer" and then set the "stack pointer" to point to the newly deallocated page.
I hope that explanation was simple =)
There's of course various optimizations you could do with that, like putting more than one address in each page (better cache usage), allowing multiple 4KiB pages to be returned simultaneously, etc..