On 10/01/10 20:28, Ed Schouten wrote:
> Andre,
>
> * Andre Oppermann wrote:
>> A splay tree is an interesting binary search tree with insertion,
>> lookup and removal performed in O(log n) *amortized* time. With
>> the *amortized* time being the crucial difference to other binary trees.
>> On ev
On 10/01/10 10:54, Andre Oppermann wrote:
> On 30.09.2010 19:51, Ivan Voras wrote:
>> On 09/30/10 18:37, Andre Oppermann wrote:
>>
>>> Both the vmmap and page table make use of splay trees to manage the
>>> entries and to speed up lookups compared to long to traverse linked
>>> lists or more memory
Andre,
* Andre Oppermann wrote:
> A splay tree is an interesting binary search tree with insertion,
> lookup and removal performed in O(log n) *amortized* time. With
> the *amortized* time being the crucial difference to other binary trees.
> On every access *including* lookup it rotates the tre
On 30.09.2010 19:51, Ivan Voras wrote:
On 09/30/10 18:37, Andre Oppermann wrote:
Both the vmmap and page table make use of splay trees to manage the
entries and to speed up lookups compared to long to traverse linked
lists or more memory expensive hash tables. Some structures though
do have an
On 30.09.2010 20:38, Alfred Perlstein wrote:
Andre,
Your observations on the effectiveness of the splay tree
mirror the concerns I have with it when I read about it.
I have always wondered though if the splay-tree algorithm
was modified to only perform rotations when a lookup required
more than
On 30.09.2010 20:01, Alan Cox wrote:
On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann wrote:
On 30.09.2010 18:37, Andre Oppermann wrote:
Just for the kick of it I decided to take a closer look at the use of
splay trees (inherited from Mach if I read the history correctly) in
the FreeBSD VM
On 09/30/10 20:38, Alfred Perlstein wrote:
> Andre,
>
> Your observations on the effectiveness of the splay tree
> mirror the concerns I have with it when I read about it.
>
> I have always wondered though if the splay-tree algorithm
> was modified to only perform rotations when a lookup required
Andre,
Your observations on the effectiveness of the splay tree
mirror the concerns I have with it when I read about it.
I have always wondered though if the splay-tree algorithm
was modified to only perform rotations when a lookup required
more than "N" traversals to reach a node.
This would se
On 09/30/10 20:01, Alan Cox wrote:
> On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann wrote:
>
>> On 30.09.2010 18:37, Andre Oppermann wrote:
>>
>>> Just for the kick of it I decided to take a closer look at the use of
>>> splay trees (inherited from Mach if I read the history correctly) in
>>>
On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann wrote:
> On 30.09.2010 18:37, Andre Oppermann wrote:
>
>> Just for the kick of it I decided to take a closer look at the use of
>> splay trees (inherited from Mach if I read the history correctly) in
>> the FreeBSD VM system suspecting an interest
On 30.09.2010 19:15, Matthew Fleming wrote:
On Thu, Sep 30, 2010 at 9:37 AM, Andre Oppermann wrote:
Just for the kick of it I decided to take a closer look at the use of
splay trees (inherited from Mach if I read the history correctly) in
the FreeBSD VM system suspecting an interesting journey.
are you aware of Summer of Code 2008 project by Mayur Shardul?
quoting: http://www.freebsd.org/projects/summerofcode-2008.html
Project: VM Algorithm Improvement
Student: Mayur Shardul
Mentor: Jeff Roberson
Summary:
A new data structure, viz. radix tree, was implemented and used for management
of
On 30.09.2010 18:37, Andre Oppermann wrote:
Just for the kick of it I decided to take a closer look at the use of
splay trees (inherited from Mach if I read the history correctly) in
the FreeBSD VM system suspecting an interesting journey.
Correcting myself regarding the history: The splay tree
On Thu, Sep 30, 2010 at 9:37 AM, Andre Oppermann wrote:
> Just for the kick of it I decided to take a closer look at the use of
> splay trees (inherited from Mach if I read the history correctly) in
> the FreeBSD VM system suspecting an interesting journey.
>
> The VM system has two major structur
Just for the kick of it I decided to take a closer look at the use of
splay trees (inherited from Mach if I read the history correctly) in
the FreeBSD VM system suspecting an interesting journey.
The VM system has two major structures:
1) the VM map which is per process and manages its address s
15 matches
Mail list logo
