Question about skiplist performance when inserts are done sorted

[Lothar Behrens]

Hi,

I use a skiplist to fill it with much data. The sorting is done by a
key of type long and the data is
anything unrelated for the algorithm.

The problem:

The data that will be inserted, consists of preordered keys. So the
skiplist will be the wrong at the
stage of inserting the data when more than about 1000 entries.

Is there a way to not build up the skip 'stack' until a new inserted
key is smaller than the biggest ?

This propably will degrade the skiplist to be a simple list. When
there were inserted sorted keys only,
a creation of the skip structure should be build up at first time of
search.

Is this possible ?

Are there any implementations I could look at ?

Thanks

Lothar

[Martin Eisenberg]

Lothar Behrens wrote:

> The data that will be inserted, consists of preordered keys. So
> the skiplist will be the wrong at the stage of inserting the
> data when more than about 1000 entries.

"Be the wrong"? I don't understand. Anyway, why not initialize the
skiplist deterministically, with the tower heights filling a dyadic
grid (like this:
http://en.wikipedia.org/wiki/Image:Dyadic_rational.svg )?

> Is there a way to not build up the skip 'stack' until a new
> inserted key is smaller than the biggest ?
>
> This propably will degrade the skiplist to be a simple list.
> When there were inserted sorted keys only, a creation of the
> skip structure should be build up at first time of search.

I don't know about self-adjusting skiplists, but you could use a
splay tree and initialize it as a list.

Martin

--
Quidquid latine scriptum est, altum videtur.

[Lothar Behrens]

Martin Eisenberg schrieb:

> Lothar Behrens wrote:
>
> > The data that will be inserted, consists of preordered keys. So
> > the skiplist will be the wrong at the stage of inserting the
> > data when more than about 1000 entries.
>
> "Be the wrong"? I don't understand. Anyway, why not initialize the
> skiplist deterministically, with the tower heights filling a dyadic
> grid (like this:
> http://en.wikipedia.org/wiki/Image:Dyadic_rational.svg )?

I know about the structure (as of the image). I think, I am wrong when
inserting pre sorted data, to do always keep the towers actual in the
skiplist.
This is what I expect from an usual skip list without the
'optimiziation'.

Maybe initializing it deterministically is missing in my
implementation.
I search for this optimization in any implementation so I could 'have
a look'.

>
> > Is there a way to not build up the skip 'stack' until a new
> > inserted key is smaller than the biggest ?
> >
> > This propably will degrade the skiplist to be a simple list.
> > When there were inserted sorted keys only, a creation of the
> > skip structure should be build up at first time of search.
>
> I don't know about self-adjusting skiplists, but you could use a
> splay tree and initialize it as a list.
>

Splay tree may be a second option. I'll try to modify the skip list.

The special case here is only tor tranferring database columns to a
file (internal / XML),
thus a simple linked list would be an option.

Thanks

Lothar

[Martin Eisenberg]

Lothar Behrens wrote:
> Martin Eisenberg schrieb:
>> Lothar Behrens wrote:
>>
>> > The data that will be inserted, consists of preordered keys.
>> > So the skiplist will be the wrong at the stage of inserting
>> > the data when more than about 1000 entries.
>>
>> "Be the wrong"? I don't understand. Anyway, why not initialize
>> the skiplist deterministically, with the tower heights filling
>> a dyadic grid (like this:
>> http://en.wikipedia.org/wiki/Image:Dyadic_rational.svg )?
>
> I know about the structure (as of the image). I think, I am
> wrong when inserting pre sorted data, to do always keep the
> towers actual in the skiplist.
> This is what I expect from an usual skip list without the
> 'optimiziation'.

You expect the randomized algorithm to build an exactly dyadic
structure? Then you should print out some real examples.

[Martin Eisenberg]

Lothar Behrens wrote:
> Martin Eisenberg schrieb:
>> Lothar Behrens wrote:
>>
>> > The data that will be inserted, consists of preordered keys.
>> > So the skiplist will be the wrong at the stage of inserting
>> > the data when more than about 1000 entries.
>>
>> "Be the wrong"? I don't understand. Anyway, why not initialize
>> the skiplist deterministically, with the tower heights filling
>> a dyadic grid (like this:
>> http://en.wikipedia.org/wiki/Image:Dyadic_rational.svg )?
>
> I know about the structure (as of the image). I think, I am
> wrong when inserting pre sorted data, to do always keep the
> towers actual in the skiplist.
> This is what I expect from an usual skip list without the
> 'optimiziation'.

You expect the randomized algorithm to build an exactly dyadic

structure? Then you should print out some real examples.

[Lothar Behrens]

I have written some code to test my container (the skiplist) and I
have not identified that
as the problem. There is a define for MAXLEVEL for the towers. It was
9 thus a maximum of
512 elements could be saved by best performance.

I have to save about 30000 thus I gone to use 20 to be far away from
that limit :-)
The speed from 10, 100, 1000, 10000, 100000 is about linear (as of my
small test application).
So it is not the problem of the skiplist.

I have done some memory savings and used more references for strings
in the container
with the same content and shorten the key that also consumes memory. I
also have removed
unneeded data from the container to reduce the memory footprint.

The bottleneck before that was about 500 and after that I have it
about 17000. This is a huge
optimisation. But I have only used 600 MB at all from my 1 GB.

Why is there still a bottleneck ?

And where did it come from (Windows XP) ?

I have put an image from the performance monitor at
http://lothar.dnsalias.net/wordpress/?cat=2

Thanks

Lothar

[Martin Eisenberg]

Lothar Behrens wrote:

> I have written some code to test my container (the skiplist) and
> I have not identified that as the problem. There is a define for
> MAXLEVEL for the towers. It was 9 thus a maximum of 512 elements
> could be saved by best performance.
>
> I have to save about 30000 thus I gone to use 20 to be far away
> from that limit :-)
> The speed from 10, 100, 1000, 10000, 100000 is about linear (as
> of my small test application).
> So it is not the problem of the skiplist.

You're explaining yourself poorly. If you've demonstrated that you
can even store thrice the items you need, then what *is* the problem?
State precisely what you see happening and which part of that
displeases you.

[Lothar Behrens]

I think, there is a memory problem. The feeled break down in speed is
later when I do
use less memory (less data in my structures). So it is not a problem
of the skiplist as of
the insert speed keeps always linear (nearly).

So the problem seems to be found :-)

Thanks, and sorry if I am explaining too poorly.

The correct question now would be, how to detect those memory
bottlenecks with Windows performance tools ?

But anyway,

Thanks

Lothar

[Martin Eisenberg]

Lothar Behrens wrote:

> The correct question now would be, how to detect those memory
> bottlenecks with Windows performance tools ?

Okay. Unfortunately, I can only hope someone else will jump in to
answer that :(