add support for "partitioned" redblack tree

[GoogleCodeExporter]

Currently there is one redblack tree to store dirty pages, and it's protected 
by a single mutex. Rusty's suggestion is to partition the tree into multiple 
internal trees, each protected by its own mutex. Then we can benchmark it and 
see if it helps increase concurrency. 

--Michi

Original issue reported on code.google.com by mutsuz...@gmail.com on 24 Jul 2011 at 1:09

[GoogleCodeExporter]

Dumping a temporary patch here. 

--Michi

Original comment by mutsuz...@gmail.com on 24 Jul 2011 at 1:13

Attachments:

• temp.patch

[GoogleCodeExporter]

Test cases for scan and min would be good (My guess is that we'll need to 
optimize min down the road...).

Also, we should probably pass "ignored" through as the second parameter of 
rbinit.  That creates pointer aliases, which might be problematic if the 
comparator tries to update its state.  However, the parameter is completely 
useless otherwise.  

Otherwise, it looks good.

Thanks.

-Rusty

Original comment by sears.ru...@gmail.com on 25 Jul 2011 at 4:04

• Added labels: Performance, Type-Enhancement
• Removed labels: Type-Defect

[GoogleCodeExporter]

Original comment by sears.ru...@gmail.com on 25 Jul 2011 at 4:06