By mistake last mail went to hackers sending it to freebsd-current
--
Hi,
Sorry for pitching in late on the discussion
Looks like I have missed many mails, Will start from this point in the
discussion
I just took a look (not in-depth though) at the patch and can't follow
your conclusio
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 01.10.2010 06:49, Matthew Dillon wrote:
I don't remember the reference but I read a comprehensive comparison
between various indexing methods about a year ago and the splay tree
did considerably better than a RB-tree. The RB-tree actually did
fairly poorly.
It heavily de
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 1 October 2010 12:49, Matthew Dillon wrote:
> What turned out to be the best indexing mechanism was a chained
> hash table whos hoppers were small linear arrays instead of single
> elements. So instead of pointer-chaining each element you have a small
> for() loop for 4-8 elements
I don't remember the reference but I read a comprehensive comparison
between various indexing methods about a year ago and the splay tree
did considerably better than a RB-tree. The RB-tree actually did
fairly poorly.
Any binary tree-like structure makes fairly poor use of cpu
For the curious, DragonflyBSD went through this back in 2005. All the
gory details are in the thread with Subject: "splay tree and red-black
tree for vm_map entry lookups" [1] While things are most likely
different now between the FreeBSD VM and the DragonflyBSD VM, it may
be worthwhile checking o
On 30.09.2010 23:44, Andre Oppermann wrote:
On 30.09.2010 20:04, Roman Divacky wrote:
On Thu, Sep 30, 2010 at 07:49:00PM +0200, Roman Divacky wrote:
On Thu, Sep 30, 2010 at 07:46:32PM +0200, Andre Oppermann wrote:
On 30.09.2010 19:24, Roman Divacky wrote:
are you aware of Summer of Code 2008
On 30.09.2010 20:04, Roman Divacky wrote:
On Thu, Sep 30, 2010 at 07:49:00PM +0200, Roman Divacky wrote:
On Thu, Sep 30, 2010 at 07:46:32PM +0200, Andre Oppermann wrote:
On 30.09.2010 19:24, Roman Divacky wrote:
are you aware of Summer of Code 2008 project by Mayur Shardul?
I remember that t
2010/9/30 Andre Oppermann :
> On 30.09.2010 19:24, Roman Divacky wrote:
>>
>> are you aware of Summer of Code 2008 project by Mayur Shardul?
>
> I remember that there was this project but I never saw any numbers
> or other outcome of it. Haven't checked p4 to look at the code
> though.
The final
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
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 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 Thu, Sep 30, 2010 at 07:49:00PM +0200, Roman Divacky wrote:
> On Thu, Sep 30, 2010 at 07:46:32PM +0200, Andre Oppermann wrote:
> > On 30.09.2010 19:24, Roman Divacky wrote:
> > >are you aware of Summer of Code 2008 project by Mayur Shardul?
> >
> > I remember that there was this project but I n
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 additional linked list to simplif
On Thu, Sep 30, 2010 at 07:46:32PM +0200, Andre Oppermann wrote:
> On 30.09.2010 19:24, Roman Divacky wrote:
> >are you aware of Summer of Code 2008 project by Mayur Shardul?
>
> I remember that there was this project but I never saw any numbers
> or other outcome of it. Haven't checked p4 to loo
On 30.09.2010 19:24, Roman Divacky wrote:
are you aware of Summer of Code 2008 project by Mayur Shardul?
I remember that there was this project but I never saw any numbers
or other outcome of it. Haven't checked p4 to look at the code
though.
--
Andre
quoting: http://www.freebsd.org/project
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.
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
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 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
24 matches
Mail list logo
