Hacker News Reader

Comment by tom_mellior | Hacker News Reader

For the benefit of others who found the description in the blog post unclear and can't or don't want to dig through the code changes themselves: "fixing the hash code and the linked list code to not use mallocs" is a bit misleading. Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload. So it's one malloc instead of two per dynamically allocated list element. This explains the "down to 80 allocations from the 115" part.

The larger gain is explained better and comes simply from stack allocation of some structures (which live in a simple array, not a linked list or hash table).

View on HN

Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload.

I wonder why this wasn't the original design; I've seen the "two-allocate" method a few times in other code and it's always seemed rather silly to allocate that separate little structure just to point to the things you're linking together anyway, so I'm curious how that way of doing it became somewhat commonplace.

Mayhaps because the structure was originally stack-allocated, or because the developer was unfamiliar or uncomfortable with intrusive datastructures. Or because the structure is used outside of linked list contexts and the memory overhead of the intrusion was considered not compensated for?

> Or because the structure is used outside of linked list contexts

That use case is possible with the particular implementation that is now used by curl:

    struct fileinfo {
      struct curl_fileinfo info;
      struct curl_llist_element list;
    };

You can use the payload (struct curl_fileinfo) outside of a list without incurring any overhead.

I think one of your other points is more likely, or simply "it was fast enough and we went for more interesting features than for such optimizations".

One of the Plan 9 C enhancements makes this even easier by permitting the fields of these structs to be accessed directly.

you can do this now in ISO C11 with the inclusion of anaonomous structures and unions.

    struct A { 
        int x, y; 
    };

    struct B {
        union {
            struct A 2d;
            struct { int x, y; };
        }
        int z;
    };

    ...

    struct B foo;
    foo.x = foo.2d.y = foo.z = 0;

you can access x and y as members of B or A.

It's the object oriented approach isn't it? So it will be natural to some (because it was taught to them that way).

Well there are situations where intrusive list pointers don't work well. If you don't control the class, then you simply can't put pointers in it. If most objects aren't ever in a list (eg. a million objects but only ten in a list at any given time), then you're wasting space. If you want to put objects in several different lists, then you have to know up front how many lists and their names, and this can become unmanageable.

You can always allocate memory big enough for a the payload plus the link structure without the links actually being inside of the payload. Just make the first part of memory contain the links and immediately afterward you have the payload.

AKA intrusive (sometimes "invasive") containers / lists.

Curl now uses the idiom where the linked list data (prev/next pointers) are inlined in the same struct that also holds the payload

And when you have a memory overwrite then your meta data is corrupted and you loose the complete list. I keep my meta data and payload in two separate list for that very reason.

So you structure your code to get more subtle errors in case of memory overwrites? "Loosing the complete list" sounds catastrophic and like something that would be easily noticed , and thus fixed.

Arranging the code to "keep trucking" in case of spurious memory overwrites seems like setting it up to be hard to debug, and having programs run in some ill-defined state where some portion of data has been overwritten but nobody notices is just super-scary.

Reply on news.ycombinator.com