Doug Lea, a computer science professor, shares Java concurrency work and writings, and the dlmalloc memory allocator.
Commenters cite his malloc allocator as a classic reference, including its mspaces, and credit his early work for Java's concurrency utilities.
Amazing survey.
Big fan of property testing.
A particularly big fan of Hedgehog.
I tried writing a Hedgehog-inspired library in Rust and realized how complex the underlying domain is.
For example, the RNG is "splittable" [1][2] which means you can take a deterministic seed and split it in two, e.g. for parallel generators to work independently but still deterministically. The effort that has gone into this feature level is a little numbing. I have an awe similar to that of the "fast inverse square root" hack when I see code like this:
-- | A predefined gamma value's needed for initializing the "root" instances of -- 'Seed'. That is, instances not produced by splitting an already existing -- instance. -- -- We choose: the odd integer closest to @2^64/φ@, where @φ = (1 + √5)/2@ is -- the golden ratio. -- goldenGamma :: Word64 goldenGamma = 0x9e3779b97f4a7c15 when realizing that those numbers don't come easily. [3]
[1]: https://hackage.haskell.org/package/hedgehog-1.4/docs/src/Hedgehog.Internal.Seed.html#Seed
[2]: https://gee.cs.oswego.edu/dl/papers/oopsla14.pdf
[3]: https://github.com/hedgehogqa/haskell-hedgehog/issues/191
Wonder why most property-testing libaries don't have features like this?
The libraries require training to use. And they're not that easy to write.
> the current state-of-the-art when it comes to property-based testing is stateful testing via a state machine model and reusing the same sequential state machine model…
Not sure if late for the party... But there is no bug int the impl. BigDecimal.toString(). It's a JVM bug. It blatantly violates the spec of the original JMM (as of Java 1.5 and backported to 1.4)
Not only that but it lacks optimization/intrinsics for String. String.length() should never/ever yield a NPE. I'd expect a process crash than adding metadata for trapping read access faults.
---
Edit: final fields have become ubiquitous even for objects that are safely published [via volatile, synchronizeed, CAS, before thread.start()]. All wrapper classes Integer, Long, etc. have them. Final fields are very much advised to be used and they do help reliability and readability by making it easy to reason about object state (i.e. it doesn't change once seen).
On x86 field fields require a compiler barrier at best as the writes are not reordered. In other words they are extremely cheap. Stuff like AtomicReference.lazySet is next to free and a welcome way to build fast concurrency primitives.
There is Doug Lea's parer[0] for the improved jmm.
There are different versions of ARM architecture with different memory models, overall ARM is considered weak.
v7 has dmb[1] only, and to my knowledge it's not cheap. Skipping dmb requires rather deep analysis, so I wonder if that was the case experienced by the poster.
ARMv8 has store-release fence but I don't know how efficient would be spamming it.
0: http://gee.cs.oswego.edu/dl/html/j9mm.html
1:…
> Compacting GC needs additional memory to have a room to allocate from, and that amount of memory is substantial unless you want to do more GC than any useful work.
Not in the case of a mark-compact collector, which works entirely in place, or a mark-region collector such as Immix [0], which only copies a small fraction of the heap.
> Also it is not free from fragmentation most of the time - the heap is defragmented only at the moment right after compaction.
An improvement would be to to perform more frequent "partial" collections, such as in the Train algorithm [1]. But some collectors (such as Immix again) avoid compaction until fragmentation is considered bad enough, which seems like a fair compromise.
> And there is internal fragmentation caused by object headers needed to store marking flags for GC - which can consume a huge amount of memory if your data is divided into tiny chunks.
The description of Doug Lea's allocator [2] suggests there are also "object headers" of a sort on allocated data in dlmalloc. You could probably steal mark bits from those headers, but it is commmon to use a separate marking bit/bytemap which is separate to space where objects are allocated, and thus has none of the fragmentation you describe.
[0] https://www.cs.utexas.edu/users/speedway/DaCapo/papers/immix-pldi-2008.pdf
[1] https://beta.cs.au.dk/Papers/Train/train.html
[2] http://gee.cs.oswego.edu/dl/html/malloc.html
Probably the fact that it eagerly coalesces newly freed blocks where high performance allocators like tcmalloc and jemalloc use slabs of fixed-sized blocks which are never coalesced. Coalescing will load adjacent blocks into cache, and it probably implies doubly linked lists where slab allocators can get away with cache-friendlier single links or bitmaps etc. (Because you probably have to remove a block from the middle of a free list if you've just coalesced it with a newly freed block). It turns out cache footprint is key for speed and scalability in allocators, so that's a big problem.
I'm embarassed to link this twice in a row now, but at one point I played around with the perf of a couple allocators, including glibc's ptmalloc. I wound up answering exactly this question, at least for some simple use cases:
http://www.andrew.cmu.edu/user/apodolsk/418/finalreport.html.
Comments in ptmalloc sources say they basically stick to the algorithm described here: http://gee.cs.oswego.edu/dl/html/malloc.html.
Excuse me if I have mis-read your sample program but it looks like you are allocating 16 bytes, then immediately freeing it, again and again in a loop. Since you're not allocating anything else, the allocate and free will happen almost immediately. Malloc() has a run time that can vary a lot depending on what has already been allocated & freed in the past, so this test is not meaningful.
Not only that, but the original doug lea's malloc has a bin specifically for 16 byte allocations: http://gee.cs.oswego.edu/dl/html/malloc.html (the smallest size), so you've specifically chosen a very fast example.
In order to properly test malloc() you have to pre-generate some pseudo random numbers for your allocation sizes, and allocate and free unpredictably. But it's more complicated than that, as in the very occasional case when malloc() has to ask the OS for more heap, that system call may not "finish" until your program first writes to that region of memory... (ie malloc() returns but hasn't finished!)
I've been diving into parallel reproducible PRNG [1] in the end I choose to have a PRNG based on xoshiro and seeding process that could take loop iteration variables [2] for reproducibility:
- [1] https://github.com/mratsim/weave/issues/147
- [2] https://github.com/mratsim/trace-of-radiance/blob/99f7d85/trace_of_radiance/support/rng.nim#L21-L53
- Usage for parallel raytracing: https://github.com/mratsim/trace-of-radiance/blob/99f7d85/trace_of_radiance/render.nim#L55-L60
Beyond the JAX paper, the Pedigree-based RNG from Leiserson was interesting as well:
- http://supertech.csail.mit.edu/papers/dprng.pdf
- https://pdfs.semanticscholar.org/a32c/3b7b8d5d3ebd594bea2d9c0935c1ac7f8e24.pdf
And Haskell's splittable RNG:
- http://www.hg.schaathun.net/research/Papers/hgs2015jfp.pdf
- http://publications.lib.chalmers.se/records/fulltext/183348/local_183348.pdf
- http://gee.cs.oswego.edu/dl/papers/oopsla14.pdf