Performace degradation over time

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Performace degradation over time

John Ruttenberg
I have a benchmark program that demonstrates significant performace
degradation over time.  Here is what this benchmark does:

    1. Create a table with a primary integer key and a blob value.
    2. Populate the table with 1M rows.  In all cases the blobs are strings
       with random lengths between 1 and 1k bytes.
    3. Loop foreer, making passes.  A pass does 1M operations each of which
       is randomly selected and can be either:
        a. an insert of an existing row, chosen at random, or
        b. an assert of a new row as in 2.
        c. Operations are grouped with BEGIN and COMMIT into batches of 1k.

Here are plots of time for each pass on a modern linux machine (fc3, >3GHz
processor, ide drives), and a modern XP machine (similar hardware).

    http://rutt.smugmug.com/photos/23341774-O.jpg

Both show an immediate and steep degradation.  Fine, it would be great to be
able to sustain 52 microseconds/operation, but even 10x that is darn good.
The disturbing thing is that the performance doesn't seem to have stabalized,
but continues to drif upward slowly.

This is using sqlite-3.1.3.  I have attached my benchmark program.  If you
want to run:

    1. Create the table with the sqlite3 command line:

        sqlite3
        create table counters (inx integer primary key, value blob);
       
    2. Run with:

        dftest5 1000000

It will run forever, printing times per pass.

Reply | Threaded
Open this post in threaded view
|

Re: Performace degradation over time

Allan Wind
On 2005-05-29T11:51:27-0400, John Ruttenberg wrote:
Content-Description: message body text
> I have a benchmark program that demonstrates significant performace
> degradation over time.  Here is what this benchmark does:
>
>     1. Create a table with a primary integer key and a blob value.
>     2. Populate the table with 1M rows.  In all cases the blobs are strings
>        with random lengths between 1 and 1k bytes.

Does your random generator run in constant time?

>     3. Loop foreer, making passes.  A pass does 1M operations each of which
>        is randomly selected and can be either:
>         a. an insert of an existing row, chosen at random, or

You mean an update?  How do you select a random row?  In particular is
that a constant (in time) operation?

>         b. an assert of a new row as in 2.

Not sure what that means.  If you select a random number, then test for
pre-existence of the row, then the chance of conflict with go up with
time.

> Here are plots of time for each pass on a modern linux machine (fc3, >3GHz
> processor, ide drives), and a modern XP machine (similar hardware).

You need to label the axis and include dimension.


/Allan

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Performace degradation over time

John Ruttenberg
Allan Wind:

> On 2005-05-29T11:51:27-0400, John Ruttenberg wrote:
> Content-Description: message body text
> > I have a benchmark program that demonstrates significant performace
> > degradation over time.  Here is what this benchmark does:
> >
> >     1. Create a table with a primary integer key and a blob value.
> >     2. Populate the table with 1M rows.  In all cases the blobs are strings
> >        with random lengths between 1 and 1k bytes.
>
> Does your random generator run in constant time?
>

I timed it.  It takes just under a second for 1M calls to rand().  This didn't
change over thousands of repetitions.


> >     3. Loop foreer, making passes.  A pass does 1M operations each of which
> >        is randomly selected and can be either:
> >         a. an insert of an existing row, chosen at random, or
>
> You mean an update?  How do you select a random row?  In particular is
> that a constant (in time) operation?
>

No, sorry.  I meant a *delete* of an existing row.  The choice takes almost no
time.


> >         b. an assert of a new row as in 2.
>
> Not sure what that means.  If you select a random number, then test for
> pre-existence of the row, then the chance of conflict with go up with
> time.
>

Again, sorry.  I posted too fast.  I meant an insert of a new row.


> > Here are plots of time for each pass on a modern linux machine (fc3, >3GHz
> > processor, ide drives), and a modern XP machine (similar hardware).
>
> You need to label the axis and include dimension.
>
>

The plots show iteration number on the x axis and number of secons on the y
axis.  So the first iteration takes about 50 seconds on linux and by the 300th
iteration, it's taking more than 600 seconds.
Reply | Threaded
Open this post in threaded view
|

Re: Performace degradation over time

Allan Wind
On 2005-05-29T18:20:33-0400, John Ruttenberg wrote:
> I timed it.  It takes just under a second for 1M calls to rand().  This didn't
> change over thousands of repetitions.

Ok.

> > You mean an update?  How do you select a random row?  In particular is
> > that a constant (in time) operation?
>
> No, sorry.  I meant a *delete* of an existing row.  The choice takes almost no
> time.

Is the ratio of inserts to deletes constant (i.e. about 1)?  If it takes
very little time to find a record to delete, doing that 0.5M times or on
every 2nd operation on average would make a difference.  Does the first
batch of inserts take the same amount of time as the nth batch? What
about batches deletes?

I have not looked at the source, but sqlite uses btrees, right?  Insert
and delete performance takes (some) logarithmic time based on number of
slots in use.  Deleted records are kept on a free list, so
"fragmentation" of the data structure account for some of this.  Growing
data set may kill your cache hit ratio (both in sqlite and os).  Not
sure how the free list works, but it may grow in length due to the
random size of your record.

Does `pragma auto_vacuum = 1` make any difference to the growth?  Or
running the vaccum command between every 1M iteration.

So no answers, just more questions :-)


/Allan

signature.asc (196 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Performace degradation over time

Gé Weijers
In reply to this post by John Ruttenberg
John,

I've tried the following test program (in pseudo code):

for(i = 0; i < 100000; i++){
  insert row with new primary key;
  rowid[i] = last_row_id();
}

for(;;){
  for(i = 0; i < 100000; i++){
    r = random(100000);
   delete from table where id =  rowid[r];
   insert row;
   rowid[r] = last_row_id();
  }
  print wall and CPU time, and file size
}

The program also issues a "COMMIT" and BEGIN every thousand iterations
through the loop;
The result is was the following:

update: 341.043948 user: 12.565154 sys: 24.393575 (85942272 bytes)
update: 384.651467 user: 13.385425 sys: 26.384125 (86450176 bytes)
update: 394.730470 user: 13.461950 sys: 26.564895 (86810624 bytes)
update: 402.420568 user: 13.602438 sys: 26.445388 (86810624 bytes)
update: 397.040290 user: 13.890028 sys: 26.192591 (86810624 bytes)
update: 377.765721 user: 13.615615 sys: 26.526867 (86810624 bytes)
update: 388.036631 user: 13.482629 sys: 26.585133 (87326720 bytes)

The number at the end is the file size.

The test program keeps the table size constant, and the CPU time does
not seem to increase like yours does. From the looks of it  the program
is only using about 10% of CPU time, so it's likely waiting from disk
I/O, which points to file system cache trashing.

When the table is filled initially all the btree pages are packed as
densely as possible. After a number of updates this will get a little
worse, so you would expect the file to grow a bit further, and the
updates to get a little slower. As you can see though I could not
reproduce your results.

Make sure that your table does not grow indefinitely, because btrees
have O(log N) search and update complexity, and your graph looks
suspiciously like a logarithmic curve.

G?


John Ruttenberg wrote:

>I have a benchmark program that demonstrates significant performace
>degradation over time.  Here is what this benchmark does:
>
>    1. Create a table with a primary integer key and a blob value.
>    2. Populate the table with 1M rows.  In all cases the blobs are strings
>       with random lengths between 1 and 1k bytes.
>    3. Loop foreer, making passes.  A pass does 1M operations each of which
>       is randomly selected and can be either:
>        a. an insert of an existing row, chosen at random, or
>        b. an assert of a new row as in 2.
>        c. Operations are grouped with BEGIN and COMMIT into batches of 1k.
>
>Here are plots of time for each pass on a modern linux machine (fc3, >3GHz
>processor, ide drives), and a modern XP machine (similar hardware).
>
>    http://rutt.smugmug.com/photos/23341774-O.jpg
>
>Both show an immediate and steep degradation.  Fine, it would be great to be
>able to sustain 52 microseconds/operation, but even 10x that is darn good.
>The disturbing thing is that the performance doesn't seem to have stabalized,
>but continues to drif upward slowly.
>
>This is using sqlite-3.1.3.  I have attached my benchmark program.  If you
>want to run:
>
>    1. Create the table with the sqlite3 command line:
>
>        sqlite3
>        create table counters (inx integer primary key, value blob);
>        
>    2. Run with:
>
>        dftest5 1000000
>
>It will run forever, printing times per pass.
>
>  
>


--
Ge' Weijers
e-mail: [hidden email]
tel:  (520)623-8542