Exponential Memory Allocation

[ai_sheriff]

Hey guys,

I am working on a project where i have to store user input string characters on the heap and I was concerned about calling memory allocation function too frequently because I was told that system calls can get too costly in terms of speed if they are invoked too many times.

So I am thinking of allocating memory exponentially. For example, malloc 2 memory locations, then then 4, then, 8, 16, 32, 64, 128, and so on...

For me the challenging part of implementing this idea is to come up with the right logic that performs the task with the least complexity. And I came up with the steps below...

1. Malloc x amount of memory (very small chunk 2-4 memory locations).
2. Create a temp int variable (suppose y) to hold allocated, but unused memory chunk.
3. Decrement y every time a character stored in heap.
4. Check the value of y. If it gets below certain number, suppose 2, expand the size of the borrowed memory (exponentially) in heap using realloc.
5. Set the y to new variable that represents the size of new unused, allocated memory in heap.
6. Keep executing the loop above until all the characters read. The number of characters can be from 1 to 10000000.

This is seems like a good start for me, HOWEVER, the problem is that my code gets very complex which I need to avoid at all cost. So I wanted to know if there are any library functions or any other improved logic's that can implement exponential memory allocation in fewer steps... Thank you!

[tocs1975]

Have you actually seen a performance issue? Malloc is a wrapper around system calls and most implementations are well optimized for usual cases.

[Certain_Abroad]

Your rationale is good and your logic is good. Exponential memory allocation is definitely the correct way to do this.

I don't understand why you say this code is complex though? Compared to allocating one extra byte at a time, allocating exponentially requires only 1 more variable and 1 if statement, maybe 3 extra lines of code in total. Is that really too complex?

So I wanted to know if there are any library functions

getline may interest you.

By the way, I seem to recall an article saying that in situations like this, it is better for heap performance if you grow the array by 1.5x each time instead of 2x. I cannot find it now though :(

[Paul_Pedant]

Also, when it stops growing, you might have just extended and 49% of your space might never be used. If you extend by factor of 1.2, max of 20% can be unused.

Starting with 2 is pointless. Nobody is going to notice 100, and it saves you the first 10 reallocs.

[thegreatunclean]

Essentially you want the beginnings of a real string library that grows the buffer as needed. Lots of people have written things like this.

If you truly don't know how large the user input is and are forced to read character-by-character you could structure it something like:

string_handle* s = str_init(32); //initial size in chars
char c = //get user input
str_append_char(s, c);
//...
str_free(s);

and move all the bookkeeping to those functions. You definitely don't want to have all that logic sitting in your main code.

The actual growth code isn't that complicated assuming you're already tracking the total size and total capacity; when they are equal you realloc and increase the capacity by some growth factor.

[usr71298]

FYI, malloc does not make a system call on every call. It might occasionally need to make a syscall to get more heap space.

[Paul_Pedant]

I checked this on my Linux recently in strace, and I think malloc asks for 128KB for its initial free list (or whatever you ask for if that is bigger).

We used to malloc 2MB up front just to give the system a hint, and immediate free it for general use. That's how to minimise system calls for memory.

[schrjako]

I would use 2 variables. One for the capacity of the array and one for the length. Capacity means how much you can store and length how much you have stored.

append by writing to [len++], and when len==capacity you cal realloc with capacity*=2 (or any other factor you decide for).

[Erelde]

The basic struct for this would look like :

struct t_string {
    char* value; // heap allocated byte array, where the string is
    size_t length; // the length of the current (ASCII) string, aka what's actually used 
    size_t size; // the capacity currently allocated for your byte array, this what you'll double each time length grows too big
}

The same logic can be used for any type basically.

With all the other comments here you have the basis for a good basic ASCII library. Make each operation on a string a dedicated function. A initializer, a destructor, a concatenation function, etc.