-4

Suppose I have a struct with the following form

typedef struct A
{
    double one;
    double two;
    void *some_ptr;
    uint8_t *array_ptr;
}

This struct has size 32 Bytes on my system. I have a single uint8_t variable that I would like to add to this struct, however, memory is at a premium (there are going to be A LOT of these structs).

Therefore, the following is not something I would like to do because it would increase my memory usage to 40 Bytes.

typedef struct B
{
    double one;
    double two;
    void *some_ptr;
    uint8_t *array_ptr;
    uint8_t my_value;
}

What I'm wondering is if I add an extra index to the array (all arrays will be the same size, however, I won't know the size until runtime) if instead I can reduce the amount of memory I'm using from 40 to 33 bytes (array will be allocated with malloc).

When malloc is called it should return an amount of memory equal to one page though I'm only guaranteed to have access to the amount of memory I request (please correct me if I'm wrong). With this in mind, my question can be boiled down to the following:

If I use malloc to allocate one extra byte for the array and store my variable at the end of the array instead of its own variable in the struct will I save memory? I ask this question because it's unclear to me how much memory malloc will actually allocate. For example, if I ask it to give me 10 bytes for one array, do I get ten bytes or 16 guaranteed (64 bit system)? If I ask it to give me 10 bytes twice for two arrays do I get 20 bytes, 32 bytes, or 24 (24 because the total has to be in chucks of 8 bytes)? Because malloc should return pointers that are multiples of 8 I believe the answer would be 32 but I'm not sure (if this is the case then in the worst case I would get the same memory usage as just adding a variable to the struct). Another way this question may be phrased is if I use malloc to allocate X bytes, how many bytes are actually used?

Note: Questions similar to the one I have, have been asked before but I don't believe they address the question that I'm actually asking. i.e.

https://stackoverflow.com/questions/5213356/malloc-how-much-memory-has-been-allocated

https://stackoverflow.com/questions/25712609/how-much-memory-does-calloc-actually-allocate
HXSP1947
  • 1,311
  • 1
  • 16
  • 39
  • [this answer](https://stackoverflow.com/a/47235897/841108) might inspire you. – Basile Starynkevitch Dec 13 '18 at 06:10
  • Depends on platform, but most likely using `malloc` for each would use more memory, as you mentioned alignments etc. You could allocate a big chunk and just assign pointers every 33 bytes if you want, but it may have other consequences. On x86 alignment doesn’t play as huge a role as on some others, but it will affect caches etc – Sami Kuhmonen Dec 13 '18 at 06:12
  • @BasileStarynkevitch I take it to mean that you're suggesting that I use flexible arrays? That way when I allocate memory for the full struct I also allocate memory for the array (This would save memory for one pointer and is a decent idea)? – HXSP1947 Dec 13 '18 at 06:14
  • Provide an [MCVE] and explain in details the kind of application you have in mind – Basile Starynkevitch Dec 13 '18 at 06:17
  • Without more context your question stays unclear. You should explain in several paragraphs why memory consumption matters that much for you. In most but not all cases, adding an additional byte field to a `struct` should not matter much. – Basile Starynkevitch Dec 13 '18 at 06:20
  • Voted to close for "too broad question" since it does not give much more additional context. – Basile Starynkevitch Dec 13 '18 at 06:29
  • The fact you could store this new `uint8_t` with the array of `uint8_t` suggests there is a one-to-one correspondence between each `struct A` and each array of `uint8_t` (and your new `my_value`). If so, it may be a good idea to make `array_ptr` a flexible array member instead of a pointer. This would eliminate 4/8 bytes from the structure, and you could insert `my_value` as a new member with no net gain of structure size. – Eric Postpischil Dec 13 '18 at 12:51
  • Another option is to request space from `malloc` in bulk, say 100,000 times the space needed for one of the `array_ptr` arrays, and dole them out yourself. This could allow you to replace the overhead of the internal data structures of `malloc` with much simpler data structures used to manage this homogeneous pool, especially if there is a pattern to your allocation, such as a fixed number of allocations for major portions of program execution or a FIFO ordering to the allocations and releases. The same management might be applied to the `struct A` allocations. – Eric Postpischil Dec 13 '18 at 12:53
  • In any case, this is [an XY problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). Your actual goal is to reduce the memory requirement, not to tinker with the internals of `malloc`. – Eric Postpischil Dec 13 '18 at 12:55

1 Answers1

3

How much memory does malloc actually allocate?

This is not specified and is implementation specific. You could dive into the source code of existing free software implementations of the C standard library (e.g. GNU libc or musl-libc) to find out how they are doing malloc. Also, malloc can fail ( see my joke-implementation of it, which is very fast) and you should test against that.

As a rule of thumb, malloc would probably use one more word at least for book-keeping purposes, and align allocated memory to probably two words (e.g. 16 bytes on x86-64). But the details are implementation and ABI specific. Since there is some overhead, you could prefer to malloc a few large memory zones (e.g of several dozens of kilobytes each) instead of many small ones (of a dozen of bytes each).

I have a single uint8_t variable that I would like to add to this struct, however, memory is at a premium (there are going to be A LOT of these structs).

Are you so sure that memory matters that much? Most computers have many gigabytes of memory, and most (but not all) applications are not extremely hungry. In the embedded world, things are different (and sometimes you are not even allowed to use any malloc); however, Linux computers are also common in the embedded case (e.g. the bus I am taking to go at work has a display driven by some Linux x86 system - sometimes the GRUB screen appears, when the disk is down).

You could consider allocating large arrays of your struct A. You could consider using indexes into a huge array, instead of pointers. You could then consider allocating the my_value in another array, etc.

You could even code your own malloc. Usually you should not, since existing malloc implementations are well tuned. You could choose an alternative malloc implementation (e.g. tcmalloc)

For example, if I ask it to give me 10 bytes for one array, do I get ten bytes or 16 guaranteed (64 bit system)?

You'll probably consume at least 16 bytes, and probably 32 bytes. But this is implementation specific. Linux has mallinfo(3) and malloc_stats(3) and other similar functions to query the state of your process. And with proc(5) you can get a lot more information about it on Linux. For example, if your Linux process has pid 1234, look into /proc/1234/maps and /proc/1234/status while it is running. See also this Linux-specific answer.

Don't forget that your development time costs too. It is likely that one day of your own work costs more than adding more DDR4 RAM to your desktop.

However there are some niche applications and domains (notably HPC, big data, genomics...) where skilled developers spend months of work to fit into a terabyte computer server.

You could use memory arenas (old GNU obstacks could be inspirational). You can query the size of a struct with sizeof and its alignment with alignof. And you probably want to read the GC handbook (even when coding manual memory management in C), because the terminology and concepts of garbage collection are relevant to your issues (since memory consumption is a whole-program property).

You could bypass malloc and directly use operating system primitives (that is, system calls) to increase your virtual address space. On Linux, you'll use mmap(2) (or the obsolete sbrk(2)) and munmap. Of course malloc uses them internally: malloc gets pages (of 4Kbytes at least) of memory using mmap and releases them using munmap. Usually free-d memory zones are kept and later reused by future mallocs.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • I'm writing code to brute force the possible system states of automaton. I will be using a lot of memory (several gigs at least). – HXSP1947 Dec 13 '18 at 06:19
  • several gigabytes is not that much. Consider also the development costs of your software. One day of your work time probably costs more than 8Gb of additional DDR4 RAM – Basile Starynkevitch Dec 13 '18 at 06:22
  • This is a research oriented project for one time use and I have limitations in the equipment available. As this information isn't directly related to the question I was asking (though I can see why it would be useful to know why I want to do what I want to do) I didn't include this. As I understand what your saying, in the worst case I won't actually do any better by using the array because malloc should return pointers that are memory aligned. Using flexible arrays though would be a good idea. – HXSP1947 Dec 13 '18 at 06:28
  • **That should go into your question, and it is *highly* relevant. You also need to give some real source code.** But of course, you should know that `malloc` has some overhead. I guess you are in HPC, then your supercomputer is running some variant of Linux, and `mallinfo` & `malloc_stats` should help – Basile Starynkevitch Dec 13 '18 at 06:30
  • "Most computers have many gigabytes of memory" --> These days most computers are embedded ones (billions per year) with maybe megabytes or a lot less. – chux - Reinstate Monica Jan 06 '19 at 22:16
  • I don't call these computers, and in that case you often don't have any `malloc`. However, I did mention embedded systems in my improved answer. – Basile Starynkevitch Jan 06 '19 at 22:23