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

Memory – Part 4: Intersec’s custom allocators

techtalk.intersec.com

Post reply on HN
Print view View original

51–60 of 62 posts

Re: Memory – Part 4: Intersec’s custom allocators

#51

Post by stormbrew »

epistasis wrote: post #39
vidarh wrote: post #35

Earlier quoted context omitted.

I haven't written much C++ in quite a few years - mostly do Ruby these days, so I'm sure I'm making some terribly embarrassing faux pas or other with the example below. But you don't need more than the C++ functionality to compose your own variations if you want more flexibility. For example: #include #include class Scope { private: typedef std::vector FV; FV fv; public: void on_return(void (* f)()) { fv.push_back(f)…

Good idea, this definitely accomplishes the same functionality, but it's done at runtime, rather than the compiler knowing all the functions at compile time. Perhaps a minor difference for most cases, though... I would still prefer a C extension... Perhaps I should just use Go these days, though ironically all these memory allocation policies are useless in a GC language.

You underestimate the compiler. This formulation might be tricky, but the version I just posted (adjacent to this post) definitely leaves the compiler knowing exactly what's going to be called when the function exits.

Re: Memory – Part 4: Intersec’s custom allocators

#52

Post by rayiner »

The thread test is janky. Most multithreaded allocators optimize for the (common) case that objects are freed by the same thread that creates them. When objects are freed by different threads than the ones that allocated them, typically some sort of slow-path is invoked.

Older allocators with per-thread caches used to behave very badly with cross-thread frees, accumulating tons of freed objects in threads that didn't necessarily allocate a lot of objects. Tcmalloc uses a garbage collection process to move those objects back to the central free list.

The test in the article, where one thread does all the allocations and another does all the frees, basically subverts the thread-caching in tcmalloc, and just tests how quickly the garbage collection process can move freed objects from the free()-thread's cache back to the central heap where they can be reused by the malloc()-thread.

Re: Memory – Part 4: Intersec’s custom allocators

#53

Post by bd_at_rivenhill »

In thinking about the t_stack allocator, I think I can see some cases for which you might want to use this instead of the alloca function, but there is not enough information to be sure if I am going down the correct mental path. Can you please explain when/why I should use t_stack instead of alloca?

Re: Memory – Part 4: Intersec’s custom allocators

#54

Post by professorTuring »

bd_at_rivenhill wrote: post #53

In thinking about the t_stack allocator, I think I can see some cases for which you might want to use this instead of the alloca function, but there is not enough information to be sure if I am going down the correct mental path. Can you please explain when/why I should use t_stack instead of alloca?

In fact, I was thinking of alloca the whole article and I really don't see the benefits of implementing a "custom solution" in detriment of a well working existing one.

It would be great to compare the results they give against alloca =)

Re: Memory – Part 4: Intersec’s custom allocators

#55

Post by fruneau »

rayiner wrote: post #52

The thread test is janky. Most multithreaded allocators optimize for the (common) case that objects are freed by the same thread that creates them. When objects are freed by different threads than the ones that allocated them, typically some sort of slow-path is invoked. Older allocators with per-thread caches used to behave very badly with cross-thread frees, accumulating tons of freed objects in threads that didn't…

I admit that test stress some corner cases (at least some cases that the allocator designer consider as corner cases). That said, malloc has no choice but supporting that use case.

A use case for such pattern is a message-posting with workers: you queue some messages that are later unqueued and processed by a different thread. This is an increasingly common pattern in modern programs. In that pattern the message is allocated in one thread (let say the main one) and processed then deallocated by another thread.

If your implementation of message allocation is malloc-based, then you will stress the exact same code paths the benchmark is stressing.

Re: Memory – Part 4: Intersec’s custom allocators

#56

Post by fruneau »

professorTuring wrote: post #54
bd_at_rivenhill wrote: post #53

In thinking about the t_stack allocator, I think I can see some cases for which you might want to use this instead of the alloca function, but there is not enough information to be sure if I am going down the correct mental path. Can you please explain when/why I should use t_stack instead of alloca?

In fact, I was thinking of alloca the whole article and I really don't see the benefits of implementing a "custom solution" in detriment of a well working existing one. It would be great to compare the results they give against alloca =)

alloca has its drawbacks. See the previous article in the series: https://techtalk.intersec.com/2013/08/memory-part-3-managing...

Re: Memory – Part 4: Intersec’s custom allocators

#57

Post by fruneau »

bd_at_rivenhill wrote: post #53

In thinking about the t_stack allocator, I think I can see some cases for which you might want to use this instead of the alloca function, but there is not enough information to be sure if I am going down the correct mental path. Can you please explain when/why I should use t_stack instead of alloca?

There are two main issues with alloca: first you cannot deallocate or reallocate the memory, you just append more data to your frame. As a consequence, it is not suitable for dynamic allocations while the t_stack is.

The second drawback is that alloca allocates on the stack, as a consequence it is limited by the size of the stack (a few megabytes on recent linux distribution, and the actual size of remaining stack depends on the callstack, since each frame consumes some stack and may have put huge buffers/alloca on it already). The t_stack has no hard-limit.

Additionally, by being totally separated from the stack, the t_stack provides a flexible alternative to the stack: you have finer-grained control on allocation/deallocation patterns.

As said in another comment, the drawbacks of alloca are explained in the previous article of the series.

Re: Memory – Part 4: Intersec’s custom allocators

#58

Post by qznc »

z3phyr wrote: post #30
qznc wrote: post #18

Earlier quoted context omitted.

There is an extended version of C, which is has this feature and is nearly as widely ported as C. They aptly named it C++.

Would C++ completely replace C, EVER? On top of that extensions like Unified Parallel C and Cello come up!

No. The C vs C++ question is simple language vs comprehensive language. A simple language might be preferred for various reasons. For example, code is easier to review, which is Linus Torvalds argument. Bindings to other languages are easier to create. Compiler is simpler, which might be important for embedded and high-reliability jobs.

Re: Memory – Part 4: Intersec’s custom allocators

#59

Post by cdman »

tptacek wrote: post #42
jbooth wrote: post #29

Earlier quoted context omitted.

Well, personally, if I'm using C, it's typically for a very narrowly defined, performance-sensitive problem. Both times I've done this in the last couple years, I found myself doing a couple big mallocs at the start and then running some tight loops over that memory with no further mallocs -- for use cases with more allocation, I'll just use whatever other language is more convenient, preferably one with a GC. But if…

That's essentially what I do in much of my C code: implement pool allocators. And that's essentially what the post we're commenting on is talking about. Incidentally, good common case for 8-byte allocations that is actually common in real-world C code: 32 bit linked list nodes (4 bytes nextptr, 4 bytes dataptr).

Hmm, are you sure that this (linked lists with small elements) is a good example which you should tell people about?

Linked lists are bad because they have big overhead (8 bytes for every element in your case - which dominates by a large margin if you store an int in each node for example) and they are really bad for CPU caches (they have very little spatial locality), thus slowing down your code.

I much rather prefer the "growing array" approach.

Re: Memory – Part 4: Intersec’s custom allocators

#60

Post by JoachimSchipper »

fruneau wrote: post #55
rayiner wrote: post #52

The thread test is janky. Most multithreaded allocators optimize for the (common) case that objects are freed by the same thread that creates them. When objects are freed by different threads than the ones that allocated them, typically some sort of slow-path is invoked. Older allocators with per-thread caches used to behave very badly with cross-thread frees, accumulating tons of freed objects in threads that didn't…

I admit that test stress some corner cases (at least some cases that the allocator designer consider as corner cases). That said, malloc has no choice but supporting that use case. A use case for such pattern is a message-posting with workers: you queue some messages that are later unqueued and processed by a different thread. This is an increasingly common pattern in modern programs. In that pattern the message is a…

You're not wrong that malloc-based message passing causes that load on malloc, but if performance of the message-passing code is important, you'd want to use a ring buffer anyway - cross-CPU or not, malloc is pretty slow.
Post reply on HN