/ Check-in [d4e0933d]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Optimized varint routines and tests added. (CVS 1380)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d4e0933dc72b66157164610e0b03f339bc535fb9
User & Date: drh 2004-05-14 16:50:06
Context
2004-05-14
19:08
More speed improvements. (CVS 1381) check-in: cf75cac9 user: drh tags: trunk
16:50
Optimized varint routines and tests added. (CVS 1380) check-in: d4e0933d user: drh tags: trunk
15:27
Performance improvements (CVS 1379) check-in: cad47917 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.136 2004/05/14 15:27:28 drh Exp $
           12  +** $Id: btree.c,v 1.137 2004/05/14 16:50:06 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
   330    330     p[0] = v>>24;
   331    331     p[1] = v>>16;
   332    332     p[2] = v>>8;
   333    333     p[3] = v;
   334    334   }
   335    335   
   336    336   /*
   337         -** Read a variable-length integer.  Store the result in *pResult.
   338         -** Return the number of bytes in the integer.
          337  +** Routines to read and write variable-length integers.
   339    338   */
   340         -static unsigned int getVarint(unsigned char *p, u64 *pResult){
   341         -  u64 x = 0;
   342         -  int n = 0;
   343         -  unsigned char c;
   344         -  do{
   345         -    c = p[n++];
   346         -    x = (x<<7) | (c & 0x7f);
   347         -  }while( (c & 0x80)!=0 );
   348         -  *pResult = x;
   349         -  return n;
   350         -}
   351         -static unsigned int getVarint32(unsigned char *p, u32 *pResult){
   352         -  u32 x = 0;
   353         -  int n = 0;
   354         -  unsigned char c;
   355         -  do{
   356         -    c = p[n++];
   357         -    x = (x<<7) | (c & 0x7f);
   358         -  }while( (c & 0x80)!=0 );
   359         -  *pResult = x;
   360         -  return n;
   361         -}
   362         -
   363         -/*
   364         -** Write a variable length integer with value v into p[].  Return
   365         -** the number of bytes written.
   366         -*/
   367         -static unsigned int putVarint(unsigned char *p, u64 v){
   368         -  int i, j, n;
   369         -  u8 buf[10];
   370         -  n = 0;
   371         -  do{
   372         -    buf[n++] = (v & 0x7f) | 0x80;
   373         -    v >>= 7;
   374         -  }while( v!=0 );
   375         -  buf[0] &= 0x7f;
   376         -  for(i=0, j=n-1; j>=0; j--, i++){
   377         -    p[i] = buf[j];
   378         -  }
   379         -  return n;
   380         -}
          339  +#define getVarint    sqlite3GetVarint
          340  +#define getVarint32  sqlite3GetVarint32
          341  +#define putVarint    sqlite3PutVarint
   381    342   
   382    343   /*
   383    344   ** Parse a cell header and fill in the CellInfo structure.
   384    345   */
   385    346   static void parseCell(
   386    347     MemPage *pPage,         /* Page containing the cell */
   387    348     unsigned char *pCell,   /* The cell */

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.232 2004/05/14 11:00:53 danielk1977 Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.233 2004/05/14 16:50:06 drh Exp $
    15     15   */
    16     16   #include "config.h"
    17     17   #include "sqlite.h"
    18     18   #include "hash.h"
    19     19   #include "parse.h"
    20     20   #include <stdio.h>
    21     21   #include <stdlib.h>
................................................................................
  1285   1285   unsigned char *sqlite3utf16to8(const void *pData, int N);
  1286   1286   void *sqlite3utf8to16be(const unsigned char *pIn, int N);
  1287   1287   void *sqlite3utf8to16le(const unsigned char *pIn, int N);
  1288   1288   void sqlite3utf16to16le(void *pData, int N);
  1289   1289   void sqlite3utf16to16be(void *pData, int N);
  1290   1290   int sqlite3PutVarint(unsigned char *, u64);
  1291   1291   int sqlite3GetVarint(const unsigned char *, u64 *);
         1292  +int sqlite3GetVarint32(const unsigned char *, u32 *);
  1292   1293   int sqlite3VarintLen(u64 v);
  1293   1294   int sqlite3AddRecordType(Vdbe*, Table*);
  1294         -
  1295         -

Changes to src/test3.c.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Code for testing the btree.c module in SQLite.  This code
    13     13   ** is not included in the SQLite library.  It is used for automated
    14     14   ** testing of the SQLite library.
    15     15   **
    16         -** $Id: test3.c,v 1.36 2004/05/11 02:10:07 danielk1977 Exp $
           16  +** $Id: test3.c,v 1.37 2004/05/14 16:50:06 drh Exp $
    17     17   */
    18     18   #include "sqliteInt.h"
    19     19   #include "pager.h"
    20     20   #include "btree.h"
    21     21   #include "tcl.h"
    22     22   #include <stdlib.h>
    23     23   #include <string.h>
................................................................................
  1025   1025     int n;
  1026   1026     u32 nData;
  1027   1027     const char *zBuf;
  1028   1028     char zStatic[1000];
  1029   1029   
  1030   1030     if( argc!=3 ){
  1031   1031       Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
  1032         -       " ID AMT
\"", 0);
         1032  +       " ID AMT
         1033  +\"", 0);
  1033   1034       return TCL_ERROR;
  1034   1035     }
  1035   1036     if( Tcl_GetInt(interp, argv[1], (int*)&pCur) ) return TCL_ERROR;
  1036   1037     if( Tcl_GetInt(interp, argv[2], &n) ) return TCL_ERROR;
  1037   1038     sqlite3BtreeDataSize(pCur, &nData);
  1038   1039     zBuf = sqlite3BtreeDataFetch(pCur, n);
  1039   1040     if( zBuf ){
................................................................................
  1140   1141     Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
  1141   1142     int argc,              /* Number of arguments */
  1142   1143     const char **argv      /* Text of each argument */
  1143   1144   ){
  1144   1145     return TCL_OK;
  1145   1146   }
  1146   1147   
         1148  +/*
         1149  +** usage:   varint_test  START  MULTIPLIER  COUNT  INCREMENT
         1150  +**
         1151  +** This command tests the sqlite3PutVarint() and sqlite3GetVarint()
         1152  +** routines, both for accuracy and for speed.
         1153  +**
         1154  +** An integer is written using PutVarint() and read back with
         1155  +** GetVarint() and varified to be unchanged.  This repeats COUNT
         1156  +** times.  The first integer is START*MULTIPLIER.  Each iteration
         1157  +** increases the integer by INCREMENT.
         1158  +**
         1159  +** This command returns nothing if it works.  It returns an error message
         1160  +** if something goes wrong.
         1161  +*/
         1162  +static int btree_varint_test(
         1163  +  void *NotUsed,
         1164  +  Tcl_Interp *interp,    /* The TCL interpreter that invoked this command */
         1165  +  int argc,              /* Number of arguments */
         1166  +  const char **argv      /* Text of each argument */
         1167  +){
         1168  +  u32 start, mult, count, incr;
         1169  +  u64 in, out;
         1170  +  int n1, n2, i;
         1171  +  unsigned char zBuf[100];
         1172  +  if( argc!=5 ){
         1173  +    Tcl_AppendResult(interp, "wrong # args: should be \"", argv[0],
         1174  +       " START MULTIPLIER COUNT INCREMENT\"", 0);
         1175  +    return TCL_ERROR;
         1176  +  }
         1177  +  if( Tcl_GetInt(interp, argv[1], (int*)&start) ) return TCL_ERROR;
         1178  +  if( Tcl_GetInt(interp, argv[2], (int*)&mult) ) return TCL_ERROR;
         1179  +  if( Tcl_GetInt(interp, argv[3], (int*)&count) ) return TCL_ERROR;
         1180  +  if( Tcl_GetInt(interp, argv[4], (int*)&incr) ) return TCL_ERROR;
         1181  +  in = start;
         1182  +  in *= mult;
         1183  +  for(i=0; i<count; i++){
         1184  +    n1 = sqlite3PutVarint(zBuf, in);
         1185  +    if( n1>9 || n1<1 ){
         1186  +      Tcl_AppendResult(interp, "PutVarint returned value out of range", 0);
         1187  +      return TCL_ERROR;
         1188  +    }
         1189  +    n2 = sqlite3GetVarint(zBuf, &out);
         1190  +    if( n1!=n2 ){
         1191  +      Tcl_AppendResult(interp, \
         1192  +         "GetVarint returned value different from PutVarint", 0);
         1193  +      return TCL_ERROR;
         1194  +    }
         1195  +    if( in!=out ){
         1196  +      Tcl_AppendResult(interp, \
         1197  +         "Value read is different from value written", 0);
         1198  +      return TCL_ERROR;
         1199  +    }
         1200  +    in += incr;
         1201  +  }
         1202  +  return TCL_OK;
         1203  +}
  1147   1204   
  1148   1205   /*
  1149   1206   ** Register commands with the TCL interpreter.
  1150   1207   */
  1151   1208   int Sqlitetest3_Init(Tcl_Interp *interp){
  1152   1209     extern int sqlite3_btree_trace;
  1153   1210     static struct {
................................................................................
  1184   1241        { "btree_payload_size",       (Tcl_CmdProc*)btree_payload_size       },
  1185   1242        { "btree_first",              (Tcl_CmdProc*)btree_first              },
  1186   1243        { "btree_last",               (Tcl_CmdProc*)btree_last               },
  1187   1244        { "btree_cursor_info",        (Tcl_CmdProc*)btree_cursor_info        },
  1188   1245        { "btree_cursor_list",        (Tcl_CmdProc*)btree_cursor_list        },
  1189   1246        { "btree_integrity_check",    (Tcl_CmdProc*)btree_integrity_check    },
  1190   1247        { "btree_breakpoint",         (Tcl_CmdProc*)btree_breakpoint         },
         1248  +     { "btree_varint_test",        (Tcl_CmdProc*)btree_varint_test        },
  1191   1249     };
  1192   1250     int i;
  1193   1251   
  1194   1252     for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
  1195   1253       Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
  1196   1254     }
  1197   1255     Tcl_LinkVar(interp, "pager_refinfo_enable", (char*)&pager3_refinfo_enable,
  1198   1256        TCL_LINK_INT);
  1199   1257     Tcl_LinkVar(interp, "btree_trace", (char*)&sqlite3_btree_trace,
  1200   1258        TCL_LINK_INT);
  1201   1259     return TCL_OK;
  1202   1260   }

Changes to src/util.c.

    10     10   **
    11     11   *************************************************************************
    12     12   ** Utility functions used throughout sqlite.
    13     13   **
    14     14   ** This file contains functions for allocating memory, comparing
    15     15   ** strings, and stuff like that.
    16     16   **
    17         -** $Id: util.c,v 1.81 2004/05/14 11:00:53 danielk1977 Exp $
           17  +** $Id: util.c,v 1.82 2004/05/14 16:50:06 drh Exp $
    18     18   */
    19     19   #include "sqliteInt.h"
    20     20   #include <stdarg.h>
    21     21   #include <ctype.h>
    22     22   
    23     23   /*
    24     24   ** If malloc() ever fails, this global variable gets set to 1.
................................................................................
  1135   1135     if( db->pVdbe!=0 ){
  1136   1136       db->magic = SQLITE_MAGIC_ERROR;
  1137   1137       return 1;
  1138   1138     }
  1139   1139     return 0;
  1140   1140   }
  1141   1141   
         1142  +/*
         1143  +** Write a 64-bit variable-length integer to memory starting at p[0].
         1144  +** The length of data write will be between 1 and 9 bytes.  The number
         1145  +** of bytes written is returned.
         1146  +**
         1147  +** A variable-length integer consists of the lower 7 bits of each byte
         1148  +** for all bytes that have the 8th bit set and one byte with the 8th
         1149  +** bit clear.
         1150  +*/
  1142   1151   int sqlite3PutVarint(unsigned char *p, u64 v){
  1143         -  int i = 0;
         1152  +  int i, j, n;
         1153  +  u8 buf[10];
         1154  +  n = 0;
  1144   1155     do{
  1145         -    p[i++] = (v & 0x7f) | 0x80;
         1156  +    buf[n++] = (v & 0x7f) | 0x80;
  1146   1157       v >>= 7;
  1147   1158     }while( v!=0 );
  1148         -  p[i-1] &= 0x7f;
  1149         -  return i;
         1159  +  buf[0] &= 0x7f;
         1160  +  for(i=0, j=n-1; j>=0; j--, i++){
         1161  +    p[i] = buf[j];
         1162  +  }
         1163  +  return n;
         1164  +}
         1165  +
         1166  +/*
         1167  +** Read a 64-bit variable-length integer from memory starting at p[0].
         1168  +** Return the number of bytes read.  The value is stored in *v.
         1169  +*/
         1170  +int sqlite3GetVarint(const unsigned char *p, u64 *v){
         1171  +  u32 x;
         1172  +  u64 x64;
         1173  +  int n;
         1174  +  unsigned char c;
         1175  +  c = p[0];
         1176  +  if( (c & 0x80)==0 ){
         1177  +    *v = c;
         1178  +    return 1;
         1179  +  }
         1180  +  x = c & 0x7f;
         1181  +  c = p[1];
         1182  +  if( (c & 0x80)==0 ){
         1183  +    *v = (x<<7) | c;
         1184  +    return 2;
         1185  +  }
         1186  +  x = (x<<7) | (c&0x7f);
         1187  +  c = p[2];
         1188  +  if( (c & 0x80)==0 ){
         1189  +    *v = (x<<7) | c;
         1190  +    return 3;
         1191  +  }
         1192  +  x = (x<<7) | (c&0x7f);
         1193  +  c = p[3];
         1194  +  if( (c & 0x80)==0 ){
         1195  +    *v = (x<<7) | c;
         1196  +    return 4;
         1197  +  }
         1198  +  x64 = (x<<7) | (c&0x7f);
         1199  +  n = 4;
         1200  +  do{
         1201  +    c = p[n++];
         1202  +    x64 = (x64<<7) | (c&0x7f);
         1203  +  }while( (c & 0x80)!=0 );
         1204  +  *v = x64;
         1205  +  return n;
  1150   1206   }
  1151   1207   
  1152         -int sqlite3GetVarint(const unsigned char *p, u64 *v){
  1153         -  u64 x = p[0] & 0x7f;
  1154         -  int n = 0;
  1155         -  while( (p[n++]&0x80)!=0 ){
  1156         -    x |= ((u64)(p[n]&0x7f))<<(n*7);
         1208  +/*
         1209  +** Read a 32-bit variable-length integer from memory starting at p[0].
         1210  +** Return the number of bytes read.  The value is stored in *v.
         1211  +*/
         1212  +int sqlite3GetVarint32(const unsigned char *p, u32 *v){
         1213  +  int n = 1;
         1214  +  unsigned char c = p[0];
         1215  +  u32 x = c & 0x7f;
         1216  +  while( (c & 0x80)!=0 ){
         1217  +    c = p[n++];
         1218  +    x = (x<<7) | (c & 0x7f);
  1157   1219     }
  1158   1220     *v = x;
  1159   1221     return n;
  1160   1222   }
  1161   1223   
         1224  +/*
         1225  +** Return the number of bytes that will be needed to store the given
         1226  +** 64-bit integer.
         1227  +*/
  1162   1228   int sqlite3VarintLen(u64 v){
  1163   1229     int i = 0;
  1164   1230     do{
  1165   1231       i++;
  1166   1232       v >>= 7;
  1167   1233     }while( v!=0 );
  1168   1234     return i;
  1169   1235   }
  1170         -

Changes to test/btree.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this script is btree database backend
    13     13   #
    14         -# $Id: btree.test,v 1.23 2004/05/09 11:51:40 drh Exp $
           14  +# $Id: btree.test,v 1.24 2004/05/14 16:50:07 drh Exp $
    15     15   
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
           19  +
           20  +# Testing of varint reading writing.
           21  +#
           22  +do_test btree-0.1 {
           23  +  btree_varint_test 0 0 500 1
           24  +} {}
           25  +do_test btree-0.2 {
           26  +  btree_varint_test 1024 1 500 1
           27  +} {}
           28  +do_test btree-0.3 {
           29  +  btree_varint_test -1 1 500 1
           30  +} {}
           31  +do_test btree-0.4 {
           32  +  btree_varint_test -1 100000 500 1
           33  +} {}
    19     34   
    20     35   # Basic functionality.  Open and close a database.
    21     36   #
    22     37   do_test btree-1.1 {
    23     38     file delete -force test1.bt
    24     39     file delete -force test1.bt-journal
    25     40     set rc [catch {btree_open test1.bt 2000 0} ::b1]