[tptacek]

This is certainly interesting work. It seems like the kinds of designs for which it would make a huge difference are also the kinds of designs that would underperform in raw C as well, though; a fair amount of memory optimization in C also involves minimizing pointers.

[arethuza]

I can remember doing some optimization in Java way back (~2001 or so) where doing this kind of thing actually made a huge difference due to locality of reference - basically allocating a huge byte array and working with that to implement an "inner" hash-table rather than the usual structure that used, at least back then.

[eropple]

Yup - I have a couple similar things in my graveyard of projects. ByteBuffers are a gross hack most of the time, but the perf is impressive when you absolutely, positively need it.

[eternalban]

> ... memory optimization in C also involves minimizing pointers.

Please elaborate. Do you mean reducing overhead via compressed address space references or offset based?

[paraboul]

Pointers are fixed size (either 32 or 64bits). When a project got bigger, it's sometimes useful to "shrink" the number of pointers you're passing around.

Nicholas Nethercote has a blog about his work on this on Firefox : https://blog.mozilla.org/nnethercote/ (e.g. https://blog.mozilla.org/nnethercote/2011/11/01/spidermonkey...)

[JoachimSchipper]

Chiefly, just using fewer pointers. That is, turn

    struct foo {
        struct bar *bar;
        struct baz *baz;
    }

into

    struct foo {
        struct bar bar;
        struct baz baz;
    }

Of course, this is not always possible - but a C program written naively/for encapsulation/flexibly tends to have a lot of places where you can perform such an optimization.

The performance win, on modern platforms, comes chiefly from reducing the number of (unpredictable/non-cached) pointer dereferences.

[pcwalton]

> The performance win, on modern platforms, comes chiefly from reducing the number of (unpredictable/non-cached) pointer dereferences.

The parenthetical is important. Pointers are just fine as long as you don't dereference them and suffer cache misses as a result.

It's also worthwhile to note that what you described is not always a worthwhile optimization, even if you can do it. If, for example, you traverse an array of the objects containing a sub-object frequently and follow the pointer to that object only rarely, it's often worthwhile to allocate it separately to improve cache locality of that traversal. This is even more important if you're doing a lot of structure copies of the outer structure; avoiding copying more bits saves a lot of time. The latter case comes up surprisingly often in my experience, and I've improved performance of code quite a few times with separate allocations and pointer indirection.

[tptacek]

Nitpick: they're fine in otherwise-reasonable code as long as they aren't shredding the cache. But there are lots of unreasonable designs that waste tons of space, further burning up locality even when the pointers aren't traversed, that are due to pointer overuse.

[pcwalton]

Yes, definitely true; sizeof(void *) and malloc slop aren't free.

[jheriko]

sizeof( void* ) is free at run-time.

if not then the compiler team should rethink their careers...

[eternalban]

Got it, thank you.

I've been experimenting with a less general segmented & offset addressed approach to deal with the same issues. Quite surprising how much semantics can be encoded in 64 bytes. Performance gains are substantial.

[paraboul]

(and also reducing the number of malloc/free calls)