Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc • Hacker News Board

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#21

Post by JoshTriplett » Thu, Jul 05, 2018, 7:53 AM UTC

mabynogy wrote: post #16

Try to do a bitmap allocator. Each word of memory has a free/used bit attached in a separate map. It allows quick resizing before or after the block without moving. It can also be optimal by reducing the fragmentation (find the best block for a given size in the map). It can be optimized with bit counting intrinsics (like popcntl()).

That works well if you allocate many blocks of the same size, or you have some other data structure that tracks which blocks belong to a specific object (such as in a filesystem). For a malloc/free implementation, however, you'd need some way to track the size of the allocation to free it later.

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#22

Post by mabynogy » Thu, Jul 05, 2018, 8:17 AM UTC

JoshTriplett wrote: post #21

mabynogy wrote: post #16

Try to do a bitmap allocator. Each word of memory has a free/used bit attached in a separate map. It allows quick resizing before or after the block without moving. It can also be optimal by reducing the fragmentation (find the best block for a given size in the map). It can be optimized with bit counting intrinsics (like popcntl()).

That works well if you allocate many blocks of the same size, or you have some other data structure that tracks which blocks belong to a specific object (such as in a filesystem). For a malloc/free implementation, however, you'd need some way to track the size of the allocation to free it later.

No. The purpose is the opposite. A map to describe the memory instead of a list of blocks. The granularity can be 1 bit to describe 1 byte (or 2/4/8...).

Recent x64 instructions to count bits from left or right can help a lot to make that fast.

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#23

Post by pletnes » Thu, Jul 05, 2018, 8:58 AM UTC

What happens if you replace the glibc malloc used in implementations of higher level languages like python/ruby/js? Aren’t these languages big on allocating small objects very often?

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#24

Post by gliptic » Thu, Jul 05, 2018, 9:04 AM UTC

mabynogy wrote: post #22

JoshTriplett wrote: post #21

Earlier quoted context omitted.

That works well if you allocate many blocks of the same size, or you have some other data structure that tracks which blocks belong to a specific object (such as in a filesystem). For a malloc/free implementation, however, you'd need some way to track the size of the allocation to free it later.

No. The purpose is the opposite. A map to describe the memory instead of a list of blocks. The granularity can be 1 bit to describe 1 byte (or 2/4/8...). Recent x64 instructions to count bits from left or right can help a lot to make that fast.

1 bit per byte would require an awful lot of memory access to find a free block. You would need something like a hierarchy of bitmaps to cut down on scanning.

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#25

Post by kev009 » Thu, Jul 05, 2018, 9:06 AM UTC

pletnes wrote: post #23

What happens if you replace the glibc malloc used in implementations of higher level languages like python/ruby/js? Aren’t these languages big on allocating small objects very often?

It works fine. jemalloc is the system malloc on FreeBSD.

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#26

Post by JoshTriplett » Thu, Jul 05, 2018, 9:23 AM UTC

mabynogy wrote: post #22

JoshTriplett wrote: post #21

Earlier quoted context omitted.

That works well if you allocate many blocks of the same size, or you have some other data structure that tracks which blocks belong to a specific object (such as in a filesystem). For a malloc/free implementation, however, you'd need some way to track the size of the allocation to free it later.

No. The purpose is the opposite. A map to describe the memory instead of a list of blocks. The granularity can be 1 bit to describe 1 byte (or 2/4/8...). Recent x64 instructions to count bits from left or right can help a lot to make that fast.

How would you implement the free function? You need some way to track how much memory to free.

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#27

Post by archi42 » Thu, Jul 05, 2018, 9:25 AM UTC

If you want to consider more allocators: We use tbbmalloc from the Intel threaded building blocks for our Linux and Windows builds. I'm not sure if the dev in charge did benchmark other allocators, but results are good (we spent less time in the allocator, program runs faster overall). Our workload varies between 2 and 8GB RAM on average with 100gb and hours or days of runtime; those improved too).

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#28

Post by mabynogy » Thu, Jul 05, 2018, 9:26 AM UTC

gliptic wrote: post #24

mabynogy wrote: post #22

Earlier quoted context omitted.

No. The purpose is the opposite. A map to describe the memory instead of a list of blocks. The granularity can be 1 bit to describe 1 byte (or 2/4/8...). Recent x64 instructions to count bits from left or right can help a lot to make that fast.

1 bit per byte would require an awful lot of memory access to find a free block. You would need something like a hierarchy of bitmaps to cut down on scanning.

No because you'll end up with the same problem elsewhere (handling blocks). If I'm correct tcmalloc memory overhead is around 4%. More overhead can be acceptable if the memory is less fragmented (less fragmentation, less cache misses, better compactness and better perfs).

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#29

Post by dullgiulio » Thu, Jul 05, 2018, 9:48 AM UTC

easytiger wrote: post #19

dingo_bat wrote: post #17

I was trying to implement my own malloc and free, but I couldn't figure out how to validate the correctness of my implementation. Does anybody know of any test suite for malloc/free? Edit: I should have read TFA.

LD_PRELOAD?

Nah, I guess the parent question is more: what sort of allocation/freeing patterns is worth measuring?

Re: Testing Memory Allocators: ptmalloc2 vs. tcmalloc vs. hoard vs. jemalloc

#30

Post by senozhatsky » Thu, Jul 05, 2018, 9:55 AM UTC

The actual allocation happens in memset() - because this is where the application page faults and jumps to the kernel. The kernel populates application's address space and returns back to user land. This surely can add a lot of noise to the test results. free() is also not very simple anymore considering all the madvise() magic it does.

It probably would be interesting to see how many page faults the application generates with tcmalloc/jemalloc/glibc/etc allocators.

-ss