3 ms·

Would you have some links to posts that talk about this style of memory management and allocation?

malkia 4y ago
Game Development still revolves around this. For example when loading a level, it used to be you have huge arena, you load your "serialized" map at one end (say top), and your other chunks at the bottom - you have some "flexibility" to pop from top or bottom, so early on you arrange for that. Alternatively you split your memory per sized big chunks, and stream in out these (works well for textures, and primed sounds - e.g. the first 64kb or 128kb of a sound file).
- deleted 4y ago
  [deleted]
aidenn0 4y ago
I don't have some links, but it's more straightforward than you might think (and TFA covers some of it). 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 12 - 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
- hobs 4y ago
  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"
  - aidenn0 4y ago
    Thanks, fixed
  - ericbarrett 4y ago
    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.
    - aidenn0 4y ago
      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.
- deleted 4y ago
  [deleted]
01100011 4y ago
Nearly everything I learned about embedded systems programming came from either Embedded Systems Magazine articles(https://www.embedded.com/embedded-systems-design-magazine-archive-2/ https://www.embedded.com/embedded-systems-design-magazine-ar...) or just being a paranoid SoB. Writing reliable systems means spending a lot of time thinking about what and how failures can occur, minimizing them and dealing with the cases you can't get rid of. Simple is nearly always better. It also helped to be an EE by education and not a CS major. CS majors can get blinded by their abstractions and forget that they're working on a real piece of HW with complex limitations which require design tradeoffs.

Game Development still revolves around this. For example when loading a level, it used to be you have huge arena, you load your "serialized" map at one end (say top), and your other chunks at the bottom - you have some "flexibility" to pop from top or bottom, so early on you arrange for that. Alternatively you split your memory per sized big chunks, and stream in out these (works well for textures, and primed sounds - e.g. the first 64kb or 128kb of a sound file).

deleted 4y ago
[deleted]

aidenn0 4y ago

I don't have some links, but it's more straightforward than you might think (and TFA covers some of it). 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 12 - 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

hobs 4y ago
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"
- aidenn0 4y ago
  Thanks, fixed
- ericbarrett 4y ago
  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.
  - aidenn0 4y ago
    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.
deleted 4y ago
[deleted]

01100011 4y ago

Nearly everything I learned about embedded systems programming came from either Embedded Systems Magazine articles(https://www.embedded.com/embedded-systems-design-magazine-archive-2/ https://www.embedded.com/embedded-systems-design-magazine-ar...) or just being a paranoid SoB. Writing reliable systems means spending a lot of time thinking about what and how failures can occur, minimizing them and dealing with the cases you can't get rid of. Simple is nearly always better. It also helped to be an EE by education and not a CS major. CS majors can get blinded by their abstractions and forget that they're working on a real piece of HW with complex limitations which require design tradeoffs.