Observer: “It Does Too Much Dynamic Allocation”. Another option

[agudpp]

First of all, congrats @munificent for that great blog / book about game patterns!

I was reading the State pattern chapter and in the section about memory allocation and fragmentation, I think an idea between list and vector is a list of chunks, where each chunk is obtained from an ObjectPool (of chunks) so we avoid memory fragmentation and we improve data locality (cache friendly) when iterate over the Observers, since iterating will be more "executed" than adding/removing observers during the execution of a game (in average). It is probably a little more complex but it could be useful and faster.

Great blog again :+1:

[munificent]

That sounds kind of like what I describe here, but maybe I'm missing what you're getting at. Does that section cover what you had in mind?

You're absolutely right that having an pool of chunks will solve fragmentation. It may help with data locality, but that depends a lot on whether or not you can iterate over them in memory order. If you just treat them like linked list nodes and chase pointers, you may still end up bouncing all over the object pool.

[agudpp]

Hi Bob, I read all the chapter, and what I was trying to comment is an approach between nodes and fixed-array. I will try to explain a little better below:

I was thinking in something like a chunk of 4 pointers (or any other "nice" number depending on how much observers per subject you will have in average). Basically, the main difference is that if you have ~N observers per subject then you will need ~(N/4)+1 chunks (i.e. you can get 4 pointers in "one memory read", or the compiler (C++) will be able to optimize it in a nicer way). You are right that you will may be jumping from chunk[0] through chunk[N/4](not contiguous) but you will be able to read all the pointers of each chunk ""at once"". Choosing the number 4 (M) is the hard part taking into account the memory and performance (trade off). If M ~ 1 => we have a list of nodes as you mention in the second part of the chapter. If M ~ MAX_NUM_OBSERVERS_PER_SUBJECT (haha big macro, but is clear :p) then you will end up with arrays / vectors (as you mention in the first part of the chapter). This approach will work better when M >= 4, if not, it have not too much sense.

Summarizing, the difference is that you (or the compiler) will be able to optimize the reads per chunk but you still have the problems when moving from one chunk to another like nodes do. I'm thinking in C/C++ only (SSE for example), I have no idea how other languages will handle this :(.

Regards, let me know what you think... Probably it doesn't have to much sense add this since is a very specific approach for particular problems..

[agudpp]

Hi Bob, how are you? After a year almost I decided to invest a little bit of time on this and I post a blog about [1] it if you want to read it. Didn't have the time to measure the mem usage but I think it is more "easy" to assume / ensure that is less than normal vectors.

Regards and congrats for the book,

[1] http://somerandideas.blogspot.com/2015/03/c-chunklist-vs-normal-lists-vs-vectors.html

[munificent]

Sorry for the very long delay! Once I finished the book, I took a bit of a break from worrying about it. :)

Yes, I think your approach makes a lot of sense. Linked lists of contiguous chunks are a pretty common way to balance the ease of insertion of linked lists with the cache friendliness of arrays. You can basically dial in your optimization by tuning the chunk size.

Ropes are a kind of similar data structure.

I don't plan to make any substantive changes to the book for a good while. Maybe I'll do a second edition in a couple of years. :) So I'll leave this open to see if I can find a way to fit in a mention of chunks when I do.

Thanks!

[agudpp]

Hi Bob!, no worries at all, I implemented one year later :p.

Yes ropes seems to follow similar logic for other purposes (insertion / deletion) but not iteration hehe.

No worries about the changes, I was just commenting an idea. Good luck with that and great book again :+1:

Salu