/ Check-in [70d304dc]
Login

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

Overview
Comment:Performance optimizations to the editdist3() function in the spellfix extension.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256:70d304dcbac4c3fd5e3b96108bffea2ce6c0db19c847397d5c5e268bb90a981d
User & Date: drh 2018-02-14 20:58:36
Context
2018-02-14
23:27
Add the --readonly option to the ".open" command in the CLI. check-in: 06870bb1 user: drh tags: trunk
20:58
Performance optimizations to the editdist3() function in the spellfix extension. check-in: 70d304dc user: drh tags: trunk
20:25
Disable assert() in the spellfix extension if not compiled with SQLITE_DEBUG. check-in: 3c53ee0f user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/misc/spellfix.c.

687
688
689
690
691
692
693

694
695
696
697
698
699
700
...
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
...
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876

877
878
879
880
881
882
883
884
885
886
887
888
    int nTo = zTo ? sqlite3_column_bytes(pStmt, 2) : 0;
    int iCost = sqlite3_column_int(pStmt, 3);

    assert( zFrom!=0 || nFrom==0 );
    assert( zTo!=0 || nTo==0 );
    if( nFrom>100 || nTo>100 ) continue;
    if( iCost<0 ) continue;

    if( pLang==0 || iLang!=iLangPrev ){
      EditDist3Lang *pNew;
      pNew = sqlite3_realloc64(p->a, (p->nLang+1)*sizeof(p->a[0]));
      if( pNew==0 ){ rc = SQLITE_NOMEM; break; }
      p->a = pNew;
      pLang = &p->a[p->nLang];
      p->nLang++;
................................................................................
  EditDist3FromString *pStr,  /* Left hand string */
  int n1,                     /* Index of comparison character on the left */
  const char *z2,             /* Right-handl comparison character */
  int n2                      /* Bytes remaining in z2[] */
){
  int b1 = pStr->a[n1].nByte;
  if( b1>n2 ) return 0;
  if( memcmp(pStr->z+n1, z2, b1)!=0 ) return 0;
  return 1;
}

/*
** Delete an EditDist3FromString objecct
*/
static void editDist3FromStringDelete(EditDist3FromString *p){
................................................................................
  }
  return pStr;
}

/*
** Update entry m[i] such that it is the minimum of its current value
** and m[j]+iCost.
**
** If the iCost is 1,000,000 or greater, then consider the cost to be
** infinite and skip the update.
*/
static void updateCost(
  unsigned int *m,
  int i,
  int j,
  int iCost
){

  assert( iCost>=0 );
  if( iCost<10000 ){
    unsigned int b = m[j] + iCost;
    if( b<m[i] ) m[i] = b;
  }
}

/*
** How much stack space (int bytes) to use for Wagner matrix in 
** editDist3Core().  If more space than this is required, the entire
** matrix is taken from the heap.  To reduce the load on the memory
** allocator, make this value as large as practical for the







>







 







|







 







<
<
<







>

|
|
|
<







687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
...
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
...
861
862
863
864
865
866
867



868
869
870
871
872
873
874
875
876
877
878
879

880
881
882
883
884
885
886
    int nTo = zTo ? sqlite3_column_bytes(pStmt, 2) : 0;
    int iCost = sqlite3_column_int(pStmt, 3);

    assert( zFrom!=0 || nFrom==0 );
    assert( zTo!=0 || nTo==0 );
    if( nFrom>100 || nTo>100 ) continue;
    if( iCost<0 ) continue;
    if( iCost>10000 ) continue;   /* Costs above 10K are considered infinite */
    if( pLang==0 || iLang!=iLangPrev ){
      EditDist3Lang *pNew;
      pNew = sqlite3_realloc64(p->a, (p->nLang+1)*sizeof(p->a[0]));
      if( pNew==0 ){ rc = SQLITE_NOMEM; break; }
      p->a = pNew;
      pLang = &p->a[p->nLang];
      p->nLang++;
................................................................................
  EditDist3FromString *pStr,  /* Left hand string */
  int n1,                     /* Index of comparison character on the left */
  const char *z2,             /* Right-handl comparison character */
  int n2                      /* Bytes remaining in z2[] */
){
  int b1 = pStr->a[n1].nByte;
  if( b1>n2 ) return 0;
  if( strncmp(pStr->z+n1, z2, b1)!=0 ) return 0;
  return 1;
}

/*
** Delete an EditDist3FromString objecct
*/
static void editDist3FromStringDelete(EditDist3FromString *p){
................................................................................
  }
  return pStr;
}

/*
** Update entry m[i] such that it is the minimum of its current value
** and m[j]+iCost.



*/
static void updateCost(
  unsigned int *m,
  int i,
  int j,
  int iCost
){
  unsigned int b;
  assert( iCost>=0 );
  assert( iCost<10000 );
  b = m[j] + iCost;
  if( b<m[i] ) m[i] = b;

}

/*
** How much stack space (int bytes) to use for Wagner matrix in 
** editDist3Core().  If more space than this is required, the entire
** matrix is taken from the heap.  To reduce the load on the memory
** allocator, make this value as large as practical for the