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

Malloc Challenge

vicsydev.blogspot.com

Post reply on HN
Print view View original

61–70 of 109 posts

Re: Malloc Challenge

#61

Post by rwmj »

EdSharkey wrote: post #41

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you descri…

This is how the minor heap in many garbage collection schemes works. eg. In OCaml (the GC I'm too intimately familiar with) allocation is just decrementing a pointer and testing whether you've hit the beginning of the minor heap, so it's extremely fast.

When the minor heap is exhausted you then take the hit of scanning the heap for objects which are still live and moving those to the major heap. If you're doing it right then most objects on the minor heap will be dead by this point so only a few will need to be moved.

A fairly common trick for games or any code with little tolerance for GC pauses is to size the minor heap large enough that every allocation required in a single frame can be satisfied from the minor heap, and then do an explicit sweep of that heap at the end of the frame / before waiting for a network message / while waiting for user interaction.

Re: Malloc Challenge

#62

Post by chrisseaton »

codr4life wrote: post #40
otabdeveloper wrote: post #33

A malloc benchmark that doesn't measure multithreaded performance is worse than useless.

Only if you insist on clinging to a general purpose, system level perspective on memory allocation. No amount of thinking and reasoning about these issues is useless.

Doesn't the benchmark also just allocate and then immediately free? I think I could specialise for that particular use pattern and make it very fast just for the benchmarks. Will that not work for some reason? A good benchmark might be a replayed set of allocate and free operations from a large real application.

Re: Malloc Challenge

#63

Post by nujabes »

I'm trying to build it in MacOS but I'm inundated with errors. For example malloc_perf.c:39:3: error: implicit declaration of function 'clock_gettime' is invalid in C99 [-Werror,-Wimplicit-function-declaration] BENCHMARK("basic", &c4malloc); ^

Re: Malloc Challenge

#64

Post by khedoros1 »

_RPM wrote: post #31
greenshackle2 wrote: post #30

Earlier quoted context omitted.

Python that looks like C? It's not a thing, I just made it up. A subset of Python that is not too painful to rewrite in C. No classes, I use namedtuples as structs, etc. I'm not sure it's a sane thing to do, arguably I should just write the thing in C in the first place, but I have more experience with Python so it's still easier to me.

Python does not look like C. The first thing I can think of is using traditional loop counters instead of the for..in construct.

Python written like Python doesn't look like C. Imagine writing in a subset of the language that translates especially cleanly into C, though. It certainly wouldn't be stylistically similar to most other Python code; it'd have more in common structurally to how the same program would be written in C.

Re: Malloc Challenge

#65

Post by wfunction »

codr4life wrote: post #46
wfunction wrote: post #44

What if I want to write a malloc that requires the size to be stored separately? (i.e. one that needs to be paired with free(ptr, length) rather than just free(ptr) for good performance.) Wouldn't that provide more flexibility in the challenge and be more useful (e.g. for C++'s std::allocator)?

The pool reference allocator does just that internally. It prefixes each allocation with a block containing the size among other things. Either base your implementation on top of that or take the idea and run with it.

You totally missed the point of my question. I was NOT asking "I have an allocator that doesn't store the buffer size; how can I use it?"

I was asking, "I don't think an allocator should need to store the buffer size internally; why not formulate the challenge so that the block size doesn't need to be stored?"

Re: Malloc Challenge

#66

Post by david-given »

nujabes wrote: post #63

I'm trying to build it in MacOS but I'm inundated with errors. For example malloc_perf.c:39:3: error: implicit declaration of function 'clock_gettime' is invalid in C99 [-Werror,-Wimplicit-function-declaration] BENCHMARK("basic", &c4malloc); ^

Looking at the implementation of libc4life, I think it's full of gcc-isms. C4DEFER() is this:

    #define _C4DEFER(code, _def)				\
      void _def() code;					\
      bool _def_trigger __attribute__((cleanup(_def)))	\
  
    #define C4DEFER(code)				\
      _C4DEFER(code, C4GSYM(def))			\
So, nested functions and gcc attributes.

Nested functions awesome, but they're a gcc extension, and only supported on some architectures anyway, and AFAIK only work if you have an executable stack, which is frowned on these days (because they have to create a callable thunk to stash the nested function's context pointer).

http://stackoverflow.com/questions/8179521/implementation-of...

My understanding is that clang doesn't support nested functions, but it does have its own non-standard extension, blocks. But of course that's still not standard C.

I'm currently writing clunky C89 code for an old compiler (and occasionally, K&R C!), and I got really excited by this library for a moment, but... nope. Non-standard. Can't use it.

Re: Malloc Challenge

#67

Post by hvidgaard »

greenshackle2 wrote: post #21

>[libc4life] is aiming for simplicity and leverage; and it makes a real effort to get there by playing on C's strengths, rather than just inventing yet another buggy Lisp. Ouch, right in the feels, I've been working on https://buildyourownlisp.com in my spare time. (EDIT: I was looking for a name for the repo, YABLisp it is.) > coding in C is a welcome therapy after seemingly wasting years exploring various ways of p…

Long term maintanance is easier with safer languages.

Re: Malloc Challenge

#68

Post by Narishma »

EdSharkey wrote: post #41

I recall reading in the last year or two a recount of how a game developer got their PS3 engine to run at 30 or 60Hz framerate by aggressive triple-buffering of their scenes. One of the interesting bits about the article was their memory allocation scheme. Each game frame they'd allocate a single huge memory pool and then allocate from it by simply incrementing a pointer into the pool. I think this is what you descri…

http://www.gdcvault.com/play/1022186/Parallelizing-the-Naugh...

This might be the talk you're referring to.

Re: Malloc Challenge

#69

Post by huhtenberg »

codr4life wrote: post #40
otabdeveloper wrote: post #33

A malloc benchmark that doesn't measure multithreaded performance is worse than useless.

Only if you insist on clinging to a general purpose, system level perspective on memory allocation. No amount of thinking and reasoning about these issues is useless.

While OP might've phrased it more politely, he's got a point - allocators that aren't designed for multithreaded use are ultimately oversimplified toy projects.

It's really not that much of a challenge to knock together a (slab + heap + free list) allocator that will perform really well single-threadedly. However it will be nearly impossible to adapt it to the multithreaded context. It is a considerably more complex task and the end result will end up looking like a rocket ship compared to a simpleton that even the best single-threaded allocator will look like.

Re: Malloc Challenge

#70

Post by _pmf_ »

nothrabannosir wrote: post #60
codr4life wrote: post #25

Earlier quoted context omitted.

Show me a software stack without those kinds of bugs; they're all written in C somewhere down the line; enormous amounts of complicated C, written by coders of varying competence. At least in my stack I can keep it simple and fix anything that needs fixing.

He/she meant: two programmers of equal skill and security conscientiousness will create less exploitable security vulnerabilities per "unit of functionality", using C and respectively, ceteris paribus . "Easier languages attract less skilled devs", "higher level languages allow you to create more complex programs", yada yada. Could all be true, but it's besides the point.

> "Easier languages attract less skilled devs", "higher level languages allow you to create more complex programs", yada yada. Could all be true, but it's besides the point.

For the armchair discourse it's beside the point, but for real-world development, it's what matters the most.

Post reply on HN