0

I use C struct to build a prefix tree, i.e. Trie. I want to use it to store a lot of number lists to get the next possible number in a given path. (For example, I have [10, 15, 17] and [10, 15, 18], then the next possible number of [10,15] is 17,18.) The problem I met is about the memory use, my each struct Trie node takes only 12 bytes(I used sizeof() to check it), and have 0.83 billion nodes in total, which should take 0.83 billion * 12 bytes = 10G memory use, but actually I used 20G memory, and I want to reduce the memory use into 10G.

I use an unsigned short to store the data for each node, unsignedn short n_child to store how many children does this node have, a pointer to his children list beginning location, and realloc a 12 bytes bigger memory space for a new node.

#pragma  pack(2)
typedef struct trie_node{
    unsigned short data;
    unsigned short n_child;
    struct trie_node * children;
} Trie;

When I have to add a new child, I use:

this_node->n_child = this_node->n_child + 1;
this_node->children = (Trie *)realloc(this_node->children, this_node->n_child * sizeof(Trie));

I want to know why the memory use is bigger than calculated and cound I reduce the memory use.

wilson
  • 21
  • 1
  • 2
    [Don't cast the result of the malloc family in C](https://stackoverflow.com/q/605845/995714) – phuclv Jun 23 '19 at 10:17
  • 1
    Nit-picking — this is tangential to your main problem. Note that you have an incipient memory leak in the line `this_node->children = (Trie *)realloc(this_node->children, this_node->n_child * sizeof(Trie));` . If `realloc()` fails, you will overwrite your previous pointer with `NULL`, losing the only reference to the previous data. – Jonathan Leffler Jun 23 '19 at 10:18
  • 3
    Each memory allocation also has some overhead. It is often 16 bytes on 64-bit systems (it will almost certainly be at least 8 bytes). Allocations are also rounded up to a convenient size, likely to a multiple of 16 bytes. Consequently, your data is occupying more like 32 bytes per allocation, rather than 12 or 16 bytes as you hope. The details depend on the implementation of `malloc()`. For example, on a Mac running macOS 10.14.5 Mojave, allocating blocks of 12 (or 14, or 16) bytes generates addresses that are 16 bytes apart. Any overhead is not visible — but I'm confident it's there. – Jonathan Leffler Jun 23 '19 at 10:26
  • @jonathan: your malloc is using a pool architecture in which small chunks are tightly packed into fixed-size allocation blocks, probably page-sized. The overhead is indeed hidden: it consists of the unused chunks in each page plus a small per-page header which includes at least a bit map of used chunks. This is a big win for applications which use a lot of small blocks and whose allocation patterns don't fragment memory. Usually, apps which do a lot of realloc calls benefit less, because realloc tends to fragment. – rici Jun 23 '19 at 14:26
  • 1
    "*have 0.83 billion nodes in total*" is you know this in advance do not realloc, but get all memory in one go. – alk Jun 23 '19 at 15:24
  • Why are you using malloc in C++ at all? How are you measuring the memory usage? – user3344003 Jun 24 '19 at 04:03
  • @user3344003 I don't see a mention of C++. – glglgl Jun 25 '19 at 08:43

1 Answers1

0

The problem here is that you are allocating very small chunks of data (the size of struct trie_node is very small, and it's about the size of the data needed by the malloc() library to manage the different allocations you do. And you call realloc() each time you add a single element. Figure this scenario, you have a chunk with, let's say 10 nodes and you add one, reallocing from 10 to 11, but as you have allocated plenty of different arrays, you don't have space to fit in the hole you have your last array, so the memory manager has to make a free hole with space for 10 nodes and allocate another with space or 11 (elsewhere).

If you have the luck of having another chunk with 9 nodes and growing to 10, then you can reuse the last hole.... but that's not normally the case, that hole is reused (partially) before there's another need to grow from 9 to 10. and this provokes that there's much fragmentation in the dynamic memory area.

The fragmentation, jointly with the fact that you use a very small node structure, is generating this overhead of 100% of the used memory.

You can alleviate this in several ways:

  • Don't realloc() by one. Just do it doubling, for example. This has two advantages: first, the chunks sizes are only powers of two, so the fragmentation level is far less, because the probability of having a valid power of two is far easier if you only have powers of two. Another good value is to grow by adding the last two used sizes (as in a fibonacci series).

  • Add a pointer to the sibling and organise your tree as linked lists... This way you will allocate all chunks the same size (memory managers are best when the sizes are the same) But be careful, you grow your structure by one pointer. Parto of what you get from one side, goes out in the other.

  • If you know in advance the average of the number of children a node will have, preallocating that average number will be interesting as it will make the chunks to be near this fixed size, so it will manage better.

Finally, there's one thing you cannot avoid, and is to have some overhead, due to the metadata the memory manager needs to allocate, apart from your data, to manage properly the heap. But the bigger are your allocations, the lower losses on this data, as the memory managers normally need some amount of data per allocation, and it doesn't depend on the allocation size.

Luis Colorado
  • 10,974
  • 1
  • 16
  • 31