Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

All About Libpas, Phil's Super Fast Malloc

github.com

Post reply on HN
Print view View original

21–30 of 87 posts

Re: All About Libpas, Phil's Super Fast Malloc

#21

Post by kbenson »

adamnemecek wrote: post #13
throwaway744678 wrote: post #9

Earlier quoted context omitted.

From the top of my head: Linux, Bourne shell...

Quoted post unavailable.

Sometimes things are named after the maker ex post facto because they need a way to distinguish it. The Bourne shell, mentioned here, is likely called that for the same reason the very first shell was called the Thompson shell, in that they were written by a single person originally and not really given a name (the original being from Ken Thompson), since they were just different (or the original) implementations of the system shell. Eventually you're going to need a way to distinguish one from the other though, right? Noting who wrote it is as good (probably better) than any other option.

Linux was probably named differently, but also probably doesn't really match whatever criteria you're using to be suspicious. It started as a hobby project to make a free and open source UNIX system, of which there were few (none?), written by one guy. There was no expectation that other people would use it for anything other than something interesting to play around with, and using a portion of your own name for your own little hobby project isn't something I would look askance at, personally, especially in an age where there was no expectation that it might grow to anything, because that was definitely not the norm at the time.

Re: All About Libpas, Phil's Super Fast Malloc

#22

Post by pizlonator »

thrtythreeforty wrote: post #17
RcouF1uZ4gsC wrote: post #8

> Consequently, passing a function pointer (or struct of function pointers), where the pointer points to an always_inline function and the callee is always_inline results in specialization akin to template monomorphization. This works to any depth; the compiler won't be satisfied until there are no more always_inline function calls. This fortuitous development in compilers allowed me to write very nice template code…

I still don't quite understand how the technique saves code size versus C++ templates, although I am quite eager to understand it since template instantiation is a thorn in my side when writing code for a microcontroller with 32KB of code space. Is the idea that the struct contains pointers to always_inline functions, and that the compiler has visibility into this at the top of the always_inline call stack, so the al…

Say you have:

    template
    void foo(T& value) { value += 42; }
There's no easy way to tell the C++ compiler, "please make only one version of foo and use callbacks to figure out what it means to += on T".

In libpas, this would be done by first creating:

    always_inline void foo(void* value, void (*add_int)(void* value, int addend))
    {
        add_int(value, 42);
    }
And then you could also create:

    never_inline void foo_outline(void* value, void (*add_int)(void* value, int addend)) { foo(value, add_int); }
Now, if you want monomorphization like C++, call foo() and pass a literal for add_int. But if you don't, then call foo_outline.

Say you have 1000 callsites to foo(), they all use different types, and 5 of those callsites are hot while the other ones are hardly ever called (maybe they only run in unusual-but-necessary situations). So, the 5 hot callsites can call foo(), and the remaining 995 cold ones cal call foo_outline().

Re: All About Libpas, Phil's Super Fast Malloc

#23

Post by verdagon »

RcouF1uZ4gsC wrote: post #8

> Consequently, passing a function pointer (or struct of function pointers), where the pointer points to an always_inline function and the callee is always_inline results in specialization akin to template monomorphization. This works to any depth; the compiler won't be satisfied until there are no more always_inline function calls. This fortuitous development in compilers allowed me to write very nice template code…

IIRC, the branch predictor can work with function pointers as well. It can sometimes mitigate problems like this, though not as completely as just monomorphizing away the run-time branching/calling like they did.

Re: All About Libpas, Phil's Super Fast Malloc

#24

Post by thrtythreeforty »

pizlonator wrote: post #22
thrtythreeforty wrote: post #17

Earlier quoted context omitted.

I still don't quite understand how the technique saves code size versus C++ templates, although I am quite eager to understand it since template instantiation is a thorn in my side when writing code for a microcontroller with 32KB of code space. Is the idea that the struct contains pointers to always_inline functions, and that the compiler has visibility into this at the top of the always_inline call stack, so the al…

Say you have: template void foo(T& value) { value += 42; } There's no easy way to tell the C++ compiler, "please make only one version of foo and use callbacks to figure out what it means to += on T". In libpas, this would be done by first creating: always_inline void foo(void* value, void (*add_int)(void* value, int addend)) { add_int(value, 42); } And then you could also create: never_inline void foo_outline(void*…

> There's no easy way to tell the C++ compiler, "please make only one version of foo and use callbacks to figure out what it means to += on T".

Partial counterpoint: you could use class polymorphism, if T is always a type you control. But you're right in general; C++ doesn't have typeclasses or some other way to create an ad-hoc vtable for, say, int.

> Now, if you want monomorphization like C++, call foo() and pass a literal for add_int. But if you don't, then call foo_outline.

Does this work through structs of function pointers? Is that the reason it's so powerful?

For example, a my_class constructor create_my_class makes the class point to foo_outline, unless it's known to be a hot type, then it points to foo. When you call create_my_class, would the compiler see the values of the pointers, and start inlining foo calls, including if you pass the my_class struct into foo as "this", continuing the inlining?

Re: All About Libpas, Phil's Super Fast Malloc

#25

Post by photochemsyn »

rq1 wrote: post #5

> Consequently, passing a function pointer (or struct of function pointers), where the pointer points to an always_inline function and the callee is always_inline results in specialization akin to template monomorphization. This works to any depth; the compiler won't be satisfied until there are no more always_inline function calls. This fortuitous development in compilers allowed me to write very nice template code…

Seems like a real tour de force of low-level memory management. Prior to seeing this my go-to for understanding custom low-level (for embedded) memory managers was this (explains the basics of stack, block, bitmap and thread-local allocation) but now I have something far more complicated to get confused about.

https://www.embedded-software-engineering.de/dynamic-memory-...

Re: All About Libpas, Phil's Super Fast Malloc

#26

Post by exikyut »

A weekend project idea I just thought of, but wouldn't be able to commentate on as well as someone more experienced in memory management:

Run a bunch of memory allocator demo programs (trivial and complex) under blinkenlights (https://justine.lol/blinkenlights/), a program execution visualizer that shows how programs interact with the stack and heap as they run.

For bonus points, proceed to explain why their visualized performance is different. :)

Re: All About Libpas, Phil's Super Fast Malloc

#27

Post by pizlonator »

thrtythreeforty wrote: post #24
pizlonator wrote: post #22

Earlier quoted context omitted.

Say you have: template void foo(T& value) { value += 42; } There's no easy way to tell the C++ compiler, "please make only one version of foo and use callbacks to figure out what it means to += on T". In libpas, this would be done by first creating: always_inline void foo(void* value, void (*add_int)(void* value, int addend)) { add_int(value, 42); } And then you could also create: never_inline void foo_outline(void*…

> There's no easy way to tell the C++ compiler, "please make only one version of foo and use callbacks to figure out what it means to += on T". Partial counterpoint: you could use class polymorphism, if T is always a type you control. But you're right in general; C++ doesn't have typeclasses or some other way to create an ad-hoc vtable for, say, int. > Now, if you want monomorphization like C++, call foo() and pass a…

Yes, it works with structs of function pointers. And it works recursively.

This works (this is slightly shorthand C, fill in the blanks yourself):

    struct config {
        void (*foo)(things bar);
        stuff (*bar)(int baz);
    };
    always_inline stuff doit(config c)
    {
        c.foo(whatever);
        return c.bar(42);
    }
    always_inline void my_foo(...) { ... }
    always_inline stuff my_bar(...) { ... }
    stuff dostuff(void)
    {
        config c;
        c.foo = my_foo; 
        c.bar = my_bar;
        return doit(c);
    }
This'll all get inlined and specialized to death.

Re: All About Libpas, Phil's Super Fast Malloc

#28

Post by pizlonator »

photochemsyn wrote: post #25
rq1 wrote: post #5

> Consequently, passing a function pointer (or struct of function pointers), where the pointer points to an always_inline function and the callee is always_inline results in specialization akin to template monomorphization. This works to any depth; the compiler won't be satisfied until there are no more always_inline function calls. This fortuitous development in compilers allowed me to write very nice template code…

Seems like a real tour de force of low-level memory management. Prior to seeing this my go-to for understanding custom low-level (for embedded) memory managers was this (explains the basics of stack, block, bitmap and thread-local allocation) but now I have something far more complicated to get confused about. https://www.embedded-software-engineering.de/dynamic-memory-...

Thank you! :-)

I always wanted to write a malloc, and this is what I came up with after 3.5 years or so.

Re: All About Libpas, Phil's Super Fast Malloc

#29

Post by IshKebab »

pizlonator wrote: post #4
lidavidm wrote: post #3

I wonder how this compares to jemalloc, mimalloc, snmalloc?

I never got a chance to compare it to those, since I was most interested in beating bmalloc. And I mainly wanted to beat it on Safari workloads. I believe bmalloc was previously compared against jemalloc and tcmalloc, also using Safari workloads, and bmalloc was significantly faster at the time.

For other people who have never heard of bmalloc - it's a custom allocator used only by WebKit. I guess it's not surprising they added one since the Mac system allocator is extremely slow. A custom allocator is pretty much a free 20% speed up on Mac (depending on your workload) but I found they made no difference on Linux. Haven't tried on Windows.

Re: All About Libpas, Phil's Super Fast Malloc

#30

Post by tialaramex »

thrtythreeforty wrote: post #12
adamnemecek wrote: post #7

I'm always suspicious of things that are named after the maker.

Like Linux, or gcc.godbolt.org? I kid, but I don't see it as a downside for software. Naming a scientific phenomenon after yourself is a red flag though, see also the Crackpot Index [1]. [1]: https://math.ucr.edu/home/baez/crackpot.html

Godbolt says Compiler Explorer right there, the fact people call it "Godbolt" is because that's the memorable name rather than because Matt Godbolt tried to name it after himself. He calls it Compiler Explorer.

You can't control what people call things. My favourite example is Blackfriars Bridge in London. When that bridge was built, it was formally named after William Pitt. But like, who cares? In what way is this bridge, Pitt's bridge? People knew where it was, the Blackfriars area of London, so too bad William Pitt, everybody called it Blackfriars Bridge. And so, that's what its name is.

The priory which is why "Blackfriars" got the name hadn't existed for two hundred years by the time the bridge was proposed. Nobody living when the bridge was finished would have ever known anybody who'd met any of the friars during their lifetime. Nevertheless that part of London had "always" been called Blackfriars, and so a bridge and a railway station built many years later are named that too.

Post reply on HN