Re:A Database Without Dynamic Memory Allocation
by hobs on Thursday October 13, 2022 @01:54PM
(#33194314)
Missing the end of "- You probably don't want to do a linear-probe for a free item in the table if N is larger than about"
Re:A Database Without Dynamic Memory Allocation
by ericbarrett on Thursday October 13, 2022 @02:10PM
(#33194466)
I was curious about that too :) My guess is 16 items (edit: OP says 12) but I'm not an embedded developer, and I'm sure it's hardware-specific.
The approach I've seen for larger fixed-sized tables is a free list: when the table is allocated, also initialize an array of the slot numbers, with an associated length index. To allocate, pop the last slot # off the array and decrement the length index. To free, push the slot # onto the end of the array and increment the length index. Checking for a free slot is then just testing for length index > 0.
Re:A Database Without Dynamic Memory Allocation
by aidenn0 on Thursday October 13, 2022 @03:22PM
(#33195344)
Yeah, a stack of free indexes is good. In the rare case of "lots of indexes, but little (extra) memory" a bitmap can be good because it's 1 bit per index rather than ⌈log2(N)⌉ bits per index and has a constant factor speed up equal to the word-size of the architecture.
1. Bound every whatever that requires memory to some value N
2. For all whatevers that can have a lifetime for your entire program, do that
3. For any whatevers that can't have a lifetime for your entire program (e.g. for a database server like TFA, a connection object would qualify), make a table of size N
4. When you need a whatever (again using a connection object as an example, when listen() returns) grap an unused entry from the table. If there is no unused entry do the appropriate thing (for a connection, it could be sending an error back to the client, just resetting the TCP connection, blocking, or logging the error and restarting the whole server[1]).
5. When you are done with a whatever (e.g. the connection is closed) return it to the table.
Those are the basics; there are some details that matter for doing this well e.g.:
- You probably don't want to do a linear-probe for a free item in the table if N is larger than about
- Don't forget that the call-stack is a form of dynamic allocation, so ensure that all recursion is bounded or you still can OOM in the form of a stack overflow.
I should also note, that for certain values of N, doing things this way is normal:
- When N=1 then it's just a global (or C "static" local variable).
- When N=(number of threads) then it's just a thread-local variable
1: The last one sounds extreme, but for a well understood system, too many connections could mean something has gone terribly wrong; e.g. if you have X client instances running for the database, using connection pools of size Y and you can have 2XY live connections in your database, exceeding N=2XY is a Bad Thing that recovering from might not be possible