6 ms·

I think it's interesting and I get that it's a simple data parser, but if I am using C I prefer performance over simplicity. The Tny structs and their string va

I think it's interesting and I get that it's a simple data parser, but if I am using C I prefer performance over simplicity. The Tny structs and their string values are individually malloc'ed, worsening the performance, so allocation and deletion is a slow process. Of course he's not the only one to do this, yajl2 also makes liberal use of malloc and free when building its node tree. One good thing to say is at least his encoding format distinguishes floats from integers and accounts for NaN and Infinity values. A first step to improving this library would be to add a SAX style parser so I could build my own representation.

Demiurge 13y ago
How much difference does sporadic malloc make these days? What is the loss in performance compared to the overhead of virtual memory, randomization and whatnot, assuming OS is also trying to optimize?
- codehero 13y ago
  Help me get on the same wavelength as you. Maybe you can tell me what is "sporadic" about Tny's malloc usage? I don't understand your second question at all. Optimizing the usage of malloc and free is no different than optimizing the run time of any algorithm. The only difference is people believe they can just abstract allocation away and rely on somebody else's code to handle it.
  - Demiurge 13y ago
    When you say "structs and their string values are individually malloc'ed, worsening the performance", I call this "sporadic". Maybe it's the wrong word, if I was to use a single word. My second question is, can you actually avoid relying on somebody else's code when you call malloc? Due to virtual memory being comprised of pages, address randomization, and other things, heap is not a continuous memory space in hardware ready to be used at the moment program runs. So, what is the cost/benefit of "individually called malloc" for each struct, as opposed to pre-allocating some space? I could be totally out of my depth, in which case ignore me ;)
    - codehero 13y ago
      My point is that people expect malloc to optimize more than it really should. I don't have the time to explain anything more to you. Look at how malloc uses the brk() function and read up on TLBs. That should get you some depth.
    - baruch 13y ago
      There are several levels at play here. malloc maintains a shared data structure that is used across cpus and must lock for access to that data structure. There are optimizations there being used with some alternative allocators such as per-cpu or per-thread pool but these only reduce the rate of locks taken. In addition after you have that virtual memory in hand you need to have physical memory behind it which entails a page fault which switches into the kernel to get you a physical page, this happens per-page. There is also the effect of physical memory layout on performance, if your memory is perfectly contiguous and your data is laid-out properly you can reap benefits from that compared to the quite likely fragmented nature of data in a heap-allocated setting. This obviously means that the applications needs to manage its memory allocations on its own but when you really care about performance these become important concepts and I too tend to write my libraries for such reuse and avoid memory allocations inside them where possible. malloc is a general purpose tool and as such needs to cater to many different environments, including multi-threaded programs so it has to lock its access to the shared data structures it holds to main
    - vidarh 13y ago
      Allocation on every struct and string value is hardly sporadic for a library designed for (de-)serialisation. Hearing that makes me think that the first thing anyone should do if using this is to profile, as there's a very real chance that malloc() will dominate CPU usage for the deserialisation in that case. The problem is that malloc() needs to be generic. It's not about never calling malloc(), but about deciding when it is necessary for your use case vs. specialized solutions tailored to your use. In many cases you may know that the allocated structure will always be de-allocated at the same time, for example, in which cases pools/arenas can outperform malloc() by a magnitude or more in the right circumstances, and can also use less memory.
- dxhdr 13y ago
  A large difference. Random mallocs in library calls completely defeat the purpose of using C in the first place. Not only for performance but for fragmentation, especially on embedded devices. It makes it impossible to use my own memory arenas and instead takes the lazy route of allocating from the global heap. Look at Jsmn for an example of how to do this sort of thing beautifully and cleanly with no global side effects.
  - Demiurge 13y ago
    What do you mean by 'own memory arena' and what is the performance (or other) difference between that and global heap?
    - alexchamberlain 13y ago
      Malloc often involves a context switch to kernel mode to grab more memory. This has improved, but still doesn't address the fragmentation issue.
    - vidarh 13y ago
      Consider that you know that certain data is always de-allocated together. An example is when a document is opened and then closed. In that case you can make a dramatic amount of difference with arenas: Often you can avoid almost any memory overhead. E.g. any structures that are allocated on opening a document, and deallocated on closure, can be allocated from larger buffers without keeping any information about the individual allocations. That can save anything up to 16-20 bytes per allocation with many malloc() implementations, and reduces typical allocation cost to incrementing a pointer and checking whether or not you need to allocate a new buffer (and the allocation cost for new buffers might be amortised over anything up to thousands of small allocations). For a practical example, there's a font library that calls malloc() to allocate structures for every single glyph when opening a font. Most of the (thousands) of allocations are 4-8 bytes. Changing that to using an arena for an application I did, cut memory usage per font to about 25%-30% and cut load time for fonts to <10% by avoiding the malloc() calls. You can achieve the same by throwing abstractions out the window and putting stuff in arrays etc. But arenas is often a very effective way of keeping the abstractions while effectively getting almost the same performance and memory usage.
Keyframe 13y ago
I agree, to mitigate mallocs context switches without refactoring the code you could malloc your own arena and use tlsf.

Demiurge 13y ago

How much difference does sporadic malloc make these days? What is the loss in performance compared to the overhead of virtual memory, randomization and whatnot, assuming OS is also trying to optimize?

codehero 13y ago
Help me get on the same wavelength as you. Maybe you can tell me what is "sporadic" about Tny's malloc usage? I don't understand your second question at all. Optimizing the usage of malloc and free is no different than optimizing the run time of any algorithm. The only difference is people believe they can just abstract allocation away and rely on somebody else's code to handle it.
- Demiurge 13y ago
  When you say "structs and their string values are individually malloc'ed, worsening the performance", I call this "sporadic". Maybe it's the wrong word, if I was to use a single word. My second question is, can you actually avoid relying on somebody else's code when you call malloc? Due to virtual memory being comprised of pages, address randomization, and other things, heap is not a continuous memory space in hardware ready to be used at the moment program runs. So, what is the cost/benefit of "individually called malloc" for each struct, as opposed to pre-allocating some space? I could be totally out of my depth, in which case ignore me ;)
  - codehero 13y ago
    My point is that people expect malloc to optimize more than it really should. I don't have the time to explain anything more to you. Look at how malloc uses the brk() function and read up on TLBs. That should get you some depth.
  - baruch 13y ago
    There are several levels at play here. malloc maintains a shared data structure that is used across cpus and must lock for access to that data structure. There are optimizations there being used with some alternative allocators such as per-cpu or per-thread pool but these only reduce the rate of locks taken. In addition after you have that virtual memory in hand you need to have physical memory behind it which entails a page fault which switches into the kernel to get you a physical page, this happens per-page. There is also the effect of physical memory layout on performance, if your memory is perfectly contiguous and your data is laid-out properly you can reap benefits from that compared to the quite likely fragmented nature of data in a heap-allocated setting. This obviously means that the applications needs to manage its memory allocations on its own but when you really care about performance these become important concepts and I too tend to write my libraries for such reuse and avoid memory allocations inside them where possible. malloc is a general purpose tool and as such needs to cater to many different environments, including multi-threaded programs so it has to lock its access to the shared data structures it holds to main
  - vidarh 13y ago
    Allocation on every struct and string value is hardly sporadic for a library designed for (de-)serialisation. Hearing that makes me think that the first thing anyone should do if using this is to profile, as there's a very real chance that malloc() will dominate CPU usage for the deserialisation in that case. The problem is that malloc() needs to be generic. It's not about never calling malloc(), but about deciding when it is necessary for your use case vs. specialized solutions tailored to your use. In many cases you may know that the allocated structure will always be de-allocated at the same time, for example, in which cases pools/arenas can outperform malloc() by a magnitude or more in the right circumstances, and can also use less memory.
dxhdr 13y ago
A large difference. Random mallocs in library calls completely defeat the purpose of using C in the first place. Not only for performance but for fragmentation, especially on embedded devices. It makes it impossible to use my own memory arenas and instead takes the lazy route of allocating from the global heap. Look at Jsmn for an example of how to do this sort of thing beautifully and cleanly with no global side effects.
- Demiurge 13y ago
  What do you mean by 'own memory arena' and what is the performance (or other) difference between that and global heap?
  - alexchamberlain 13y ago
    Malloc often involves a context switch to kernel mode to grab more memory. This has improved, but still doesn't address the fragmentation issue.
  - vidarh 13y ago
    Consider that you know that certain data is always de-allocated together. An example is when a document is opened and then closed. In that case you can make a dramatic amount of difference with arenas: Often you can avoid almost any memory overhead. E.g. any structures that are allocated on opening a document, and deallocated on closure, can be allocated from larger buffers without keeping any information about the individual allocations. That can save anything up to 16-20 bytes per allocation with many malloc() implementations, and reduces typical allocation cost to incrementing a pointer and checking whether or not you need to allocate a new buffer (and the allocation cost for new buffers might be amortised over anything up to thousands of small allocations). For a practical example, there's a font library that calls malloc() to allocate structures for every single glyph when opening a font. Most of the (thousands) of allocations are 4-8 bytes. Changing that to using an arena for an application I did, cut memory usage per font to about 25%-30% and cut load time for fonts to <10% by avoiding the malloc() calls. You can achieve the same by throwing abstractions out the window and putting stuff in arrays etc. But arenas is often a very effective way of keeping the abstractions while effectively getting almost the same performance and memory usage.

Keyframe 13y ago

I agree, to mitigate mallocs context switches without refactoring the code you could malloc your own arena and use tlsf.