Strategy for placement / free placement of small objects

Question

I play with a specific caching algorithm, which is somewhat complicated. In principle, he needs to allocate a lot of small objects (double arrays, from 1 to 256 elements), with objects accessible through the displayed value, map[key] = array . the time to the initialized array can be quite large, usually more than 10 thousand processor cycles.

By lots, I mean about a gigabyte in general. objects, you may need to pop up / click as necessary, usually in random places, one object at a time. the lifetime of the object is usually long, minutes or more, however, the object can be distributed / released several times during the duration of the program.

What would be a good strategy to avoid memory fragmentation while maintaining a reasonable dedicated disadaptation rate?

I use C ++, so I can use new and malloc. Thanks.

I know that such issues on the website, the efficient distribution of many short-lived small objects are somewhat different, thread safety is not an immediate problem for me.

my development platform is Intel Xeon, the Linux operating system. Ideally, I would like to work with PPC linux, but for me this is not the most important.

Answer 1

Create a slotted splitter:

Allocator is created with many pages of memory, each of which has the same size (512k, 256k, the size must be configured for your use).

The first time an object requests this allocator for memory, it allocates a page. Selecting a page consists of removing it from the free list (without searching, all pages of the same size) and setting the size of the objects that will be highlighted on this page. As a rule, this size is calculated by taking the requested size and rounding it to the nearest power 2. Subsequent distributions of the same size require only a little math pointer and increase the number of objects on the page.

Fragmentation is prevented because the slots are the same size and can be overwritten in subsequent distributions. Efficiency is maintained (it improves in some cases), because there is no memheader on the distribution (which is very important when the distributions are small, when the distributions become large, this allocator starts to spend almost 50% of the available memory).

Both allocations and deallocations can be performed in constant time (without searching for a free list for the correct slots). The only tricky part about releasing is that you usually don’t want the memheader to precede the distribution, so you need to figure out the page and index on the page yourself ... on Saturday, and I didn’t have my coffee, so I don’t have no good tips on how to do this, but it's easy enough to understand from the freed address.

Edit: this answer is a bit long. As usual, boost has a back.

Answer 2

If you can predict the size of the allocated object in advance, it is probably best for you to go with a linearly distributed chunk of memory and your own custom allocator (as suggested by @Kerido). To this, I would add that the most effective method would be zeroing and swap for positions within the distribution, rather than worrying about redistributing and compacting the array (leave dead space between distributions), so you do not need to deal with index updates and maintenance index .

If you can break up your objects in advance (i.e. you know that you have elements of non-fixed size, but the group is easy) divide them into buckets and pre-allocate pieces of memory in each bucket and replace the elements in the corresponding bucket, if your objects can To resize throughout their entire life cycle, which may be difficult to do, carefully consider this approach.

Answer 3

If you know the maximum size of your arrays, you can use your own allocator. You will have to write the dispenser class yourself. What he should do is select several memory blocks at once and transfer them to the linked list. Each time you need to instantiate an object, you remove the tail from the list. Each time an object needs to be freed, you add an entry to the list.

EDIT: here is a sample from Bjarne Stroustrup C ++ Programming Language, 3rd Edition :

 class Pool { private: struct Link { Link * next; }; struct Chunk { enum {size = 8*1024-16}; Chunk * next; char mem[size]; }; private: Chunk * chunks; const unsigned int esize; Link * head; private: Pool (const Pool &) { } // copy protection void operator = (Pool &) { } // copy protection public: // sz is the size of elements Pool(unsigned int sz) : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz), head(0), chunks(0) { } ~Pool() { Chunk * n = chunks; while(n) { Chunk * p = n; n = n->next; delete p; } } public: // allocate one element void * alloc() { if(head == 0) grow(); Link * p = head; head = p->next; return p; } // put an element back into the pool void free(void * b) { Link * p = static_cast<Link*>(b); p->next = head; //put b back as first element head = p; } private: // make pool larger void grow() { Chunk* n = new Chunk; n->next = chunks; chunks = n; const int nelem = Chunk::size / esize; char * start = n->mem; char * last = &start [ (nelem - 1) * esize ]; for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize); reinterpret_cast<Link *>(last)->next = 0; head = reinterpret_cast<Link *>(start); } };