Maple Tree "RFC" Patches Sent Out As New Data Structure To Help With Linux Performance

[phoronix]

Phoronix: Maple Tree "RFC" Patches Sent Out As New Data Structure To Help With Linux Performance

For over the past year there has been work on the new "Maple Tree" data structure led by Oracle for the Linux kernel and this week marked the patches being sent out in "request for comments" (RFC) form with the aim still on helping the kernel performance...

http://www.phoronix.com/scan.php?page=news_item&px=Maple-Tree-Linux-RFC

[cl333r]

TMI, it can do "read-copy-update" from multiple threads without synchronization?? Can anyone explain in layman's terms how this is possible?

[twiked]

Thank you Michael for sharing such technical highlight of the kernel.

[OneTimeShot]

TMI, it can do "read-copy-update" from multiple threads without synchronization?? Can anyone explain in layman's terms how this is possible?

The basic principle is that the hardware guarantees atomic read/writes of 64 bit values (so if two threads access a single pointer in memory you get a coherent result - you don't get 32bits of "new" data, 32 bits of "old" data).

In cases where lots of threads that read a structure and very few modify it, you can make a copy of the structure change the copy, and use the atomic write of the pointer without having to lock the read threads. You then "wait" for a period of time before freeing the original memory (usually there is a higher-level way to determine when this is safe to do).

Basically it means if all you are doing is reading a structure, you don't actually need to lock it.

[skeevy420]

The Maples have formed a Union. Are they demanding equal rights?

TMI, it can do "read-copy-update" from multiple threads without synchronization?? Can anyone explain in layman's terms how this is possible?

By hatchet, axe, and saw.

I swear, Rush has an answer for everything in life.

[zerothruster]

I assume that CS people understand the naming, but for the rest of us is there any clue, please ?

I can think of leaves which become colourful before they fall, and for guitars 'flamed' tops and torrified (roasted) maple necks, but looking on wikipedia only pointed me to articles about real trees.

[f0rmat]

By hatchet, axe, and saw.

You forgot chainsaw...my Stihl chainsaw works far faster than the other three!

[f0rmat]

I assume that CS people understand the naming, but for the rest of us is there any clue, please ?

I can think of leaves which become colourful before they fall, and for guitars 'flamed' tops and torrified (roasted) maple necks, but looking on wikipedia only pointed me to articles about real trees.

Maybe this will help:

I have a maple tree in my backyard. It was being denied the earth_kernal resources sun_light and earth_nutrients by rogue sumac_bushes and improperly sandboxed poison_oak_vines from my neighbors improperly sandboxed yard. Utilizing chain_saw and clipper processes, I was able to eliminate the resource bleeding caused by sumac_bushes and poison_oak_vines. In addition, I also cut some of the lower level maple_limbs because they reduced the headroom available when I executed the mow_grass process. Eliminating the rogue sumac_bushes and sandboxing the poison_oak_vines also helped allow better and more efficient running of the wife_outdoors_process as this process has a known susceptability and vulnerability to bee_sting_allergy (the bug bees are heavily associated with blooming sumac_bushes) and the rogue_poison_oak_allergy. The wife_outdoors_process is running much more smoothly now which has significantly eased my workload.

In all seriousness, this development appears interesting.

[F.Ultra]

I assume that CS people understand the naming, but for the rest of us is there any clue, please ?

I can think of leaves which become colourful before they fall, and for guitars 'flamed' tops and torrified (roasted) maple necks, but looking on wikipedia only pointed me to articles about real trees.

The term "maple tree" seems by all accounts to be completely arbitrarily and does not come from any technical meaning. The author of it calls them "the sweetest data structure" so it just sounds like the author likes maple syrup and needed a tree like name for his new tree structure.

TMI, it can do "read-copy-update" from multiple threads without synchronization?? Can anyone explain in layman's terms how this is possible?

That you have always been able to do with RCU, you copy the data by reading it then you update your copy, then you update the pointer to point to your new copy and later you free the original after a time at when you are "guaranteed" that no other thread no longer are referring to the original.

[ed31337]

I assume that CS people understand the naming, but for the rest of us is there any clue, please ?

Maple tree software:
The code is very big, heavy, and sometimes difficult to climb due to its size. It is very beautiful, but brittle. Known to occassionally suddenly drop a huge branch when things get cold, wet and windy.