Linux's Vmalloc Seeing “Large Performance Benefits” with 5.2 Kernel Changes

https://www.phoronix.com/scan.php?page=news_item&px=Linux-5.2-vmalloc-Performance

by gmiller123456 • 7 years ago

109 14 7 years ago

saagarjha• 7 years ago

Currently an allocation of the new VA area is done over busy list iteration until a suitable hole is found between two busy areas. Therefore each new allocation causes the list being grown.

Sounds accidentally quadratic?

kazinator3• 7 years ago

Sounds like "vmalloc won't be heavily churned, unlike mmap, so who cares".

egberts1• 7 years ago

I see big boost for high-speed network drivers.

viraptor• 7 years ago

Why? I expect all high speed network drivers to be already zero-alloc in their sending path. We have zero-copy interfaces as well. Is any network operation really held up by allocs anymore?

cesarb• 7 years ago

And even if they did allocate in the send or receive path, it would probably be with kmalloc (possibly with GFP_ATOMIC), not with vmalloc.

Unklejoe• 7 years ago

How come? Are skbuffs allocated with vmalloc? I thought they were allocated from low memory.

kazinator3• 7 years ago

Drivers mostly allocate things from kmalloc, not vmalloc. vmalloc is only used for large allocations that exceed the maximum size that kmalloc can provide. It's traditionally not expected to "churn" either.

One use for vmalloc is for allocating loadable modules: when you insmod a driver, the space comes from vmalloc. Needless to say, there are few use cases for inserting and removing a driver thousands of times per second.

ncmncm2• 7 years ago

Still pointer-chasing, I see. It is remarkable that performance was ever tolerable. Probably the need to zero the pages before delivering them to user space masks almost any amount of inefficiency.

namibj• 7 years ago

I wish they would consider using cacheline sized B+ trees instead of dumb RB trees. The latter are not making proper use of pipelined superscalar processors (AKA any modern CPU that can run at over 1 GHz).

Circuits• 7 years ago

Couldn't you (or someone) write the code and submit it for approval. I was under the impression anyone could hack on the kernel (fairly new to Linux) and make submissions for review.

olliej• 7 years ago

Sorry my reading of this is that they had an important allocator using a O(N) free-block search? That makes lots of algorithms and operations become quadratic really easily - especially given no one expects linear allocation cost.

RB tree is an interesting choice, presumably there’s a benefit vs btrees (maybe reduced metadata cost?)

It’s also kind of frustrating when articles like this say things like “up to X% faster”. That’s way underselling it: this is asymptotically faster - the performance increase gets larger and larger over time, it’s not a simple multiplier :-/

kazinator3• 7 years ago

It uses a red-black tree that keeps blocks sorted by their offsets in pair with linked list keeping the free space in order of increasing addresses.

I.e. what has been used by the regular mmap for user space allocations for like two decades.

Linux's Vmalloc Seeing “Large Performance Benefits” with 5.2 Kernel Changes

Related Stories