SQLite

Check-in [11dd05e598]
Login

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

Overview
Comment:Attempt to use two cores to do sorting. Unfortunately, instead of making sorts go faster as was hoped, this changes slows sorting down by about 10%. (Later:) The previous measurement was compiled using -pg. When compiled using -Os, this new code is roughly 10% faster than the original.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | threads-sort-ex1
Files: files | file ages | folders
SHA1: 11dd05e5984f0d5f98052458b94cbaf7d18c2e8f
User & Date: drh 2012-08-16 20:05:43.061
Original Comment: Attempt to use two cores to do sorting. Unfortunately, instead of making sorts go faster as was hoped, this changes slows sorting down by about 10%.
Context
2012-08-20
12:36
Changes to the thread routines to disable them when threading is turned off using sqlite3_config(). (check-in: 555fc07efd user: drh tags: threads-sort-ex1)
2012-08-16
20:05
Attempt to use two cores to do sorting. Unfortunately, instead of making sorts go faster as was hoped, this changes slows sorting down by about 10%. (Later:) The previous measurement was compiled using -pg. When compiled using -Os, this new code is roughly 10% faster than the original. (check-in: 11dd05e598 user: drh tags: threads-sort-ex1)
11:24
Update the threads branch to include all the latest trunk changes. (check-in: f4125771e2 user: drh tags: threads)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/vdbesort.c.
101
102
103
104
105
106
107

108
109
110
111
112
113
114
  int nPMA;                       /* Number of PMAs stored in pTemp1 */
  int mnPmaSize;                  /* Minimum PMA size, in bytes */
  int mxPmaSize;                  /* Maximum PMA size, in bytes.  0==no limit */
  VdbeSorterIter *aIter;          /* Array of iterators to merge */
  int *aTree;                     /* Current state of incremental merge */
  sqlite3_file *pTemp1;           /* PMA file 1 */
  SorterRecord *pRecord;          /* Head of in-memory record list */

  UnpackedRecord *pUnpacked;      /* Used to unpack keys */
};

/*
** The following type is an iterator for a PMA. It caches the current key in 
** variables nKey/aKey. If the iterator is at EOF, pFile==0.
*/







>







101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
  int nPMA;                       /* Number of PMAs stored in pTemp1 */
  int mnPmaSize;                  /* Minimum PMA size, in bytes */
  int mxPmaSize;                  /* Maximum PMA size, in bytes.  0==no limit */
  VdbeSorterIter *aIter;          /* Array of iterators to merge */
  int *aTree;                     /* Current state of incremental merge */
  sqlite3_file *pTemp1;           /* PMA file 1 */
  SorterRecord *pRecord;          /* Head of in-memory record list */
  int nRecord;                    /* Number of elements on the pRecord list */
  UnpackedRecord *pUnpacked;      /* Used to unpack keys */
};

/*
** The following type is an iterator for a PMA. It caches the current key in 
** variables nKey/aKey. If the iterator is at EOF, pFile==0.
*/
383
384
385
386
387
388
389
390

391
392
393
394
395
396
397

398
399
400
401
402
403
404
** has been allocated and contains an unpacked record that is used as key2.
*/
static void vdbeSorterCompare(
  const VdbeCursor *pCsr,         /* Cursor object (for pKeyInfo) */
  int bOmitRowid,                 /* Ignore rowid field at end of keys */
  const void *pKey1, int nKey1,   /* Left side of comparison */
  const void *pKey2, int nKey2,   /* Right side of comparison */
  int *pRes                       /* OUT: Result of comparison */

){
  KeyInfo *pKeyInfo = pCsr->pKeyInfo;
  VdbeSorter *pSorter = pCsr->pSorter;
  UnpackedRecord *r2 = pSorter->pUnpacked;
  int i;

  if( pKey2 ){

    sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, r2);
  }

  if( bOmitRowid ){
    r2->nField = pKeyInfo->nField;
    assert( r2->nField>0 );
    for(i=0; i<r2->nField; i++){







|
>


<
<



>







384
385
386
387
388
389
390
391
392
393
394


395
396
397
398
399
400
401
402
403
404
405
** has been allocated and contains an unpacked record that is used as key2.
*/
static void vdbeSorterCompare(
  const VdbeCursor *pCsr,         /* Cursor object (for pKeyInfo) */
  int bOmitRowid,                 /* Ignore rowid field at end of keys */
  const void *pKey1, int nKey1,   /* Left side of comparison */
  const void *pKey2, int nKey2,   /* Right side of comparison */
  int *pRes,                      /* OUT: Result of comparison */
  UnpackedRecord *r2              /* Space to hold the unpacked Key2 record */
){
  KeyInfo *pKeyInfo = pCsr->pKeyInfo;


  int i;

  if( pKey2 ){
    assert( r2!=0 );
    sqlite3VdbeRecordUnpack(pKeyInfo, nKey2, pKey2, r2);
  }

  if( bOmitRowid ){
    r2->nField = pKeyInfo->nField;
    assert( r2->nField>0 );
    for(i=0; i<r2->nField; i++){
441
442
443
444
445
446
447
448
449
450

451
452
453
454
455
456
457

  if( p1->pFile==0 ){
    iRes = i2;
  }else if( p2->pFile==0 ){
    iRes = i1;
  }else{
    int res;
    assert( pCsr->pSorter->pUnpacked!=0 );  /* allocated in vdbeSorterMerge() */
    vdbeSorterCompare(
        pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res

    );
    if( res<=0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
  }







<

|
>







442
443
444
445
446
447
448

449
450
451
452
453
454
455
456
457
458

  if( p1->pFile==0 ){
    iRes = i2;
  }else if( p2->pFile==0 ){
    iRes = i1;
  }else{
    int res;

    vdbeSorterCompare(
        pCsr, 0, p1->aKey, p1->nKey, p2->aKey, p2->nKey, &res, 
        pSorter->pUnpacked
    );
    if( res<=0 ){
      iRes = i1;
    }else{
      iRes = i2;
    }
  }
543
544
545
546
547
548
549
550

551
552
553
554
555
556
557
558

559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576































































577
578
579
580
581
582
583
584
585




586




587
588
589
590
591
592

593
594
595
596
597
598
599

600
601
602
603
604


605
606


607
608
609
610
611
612
613
614
615
616
617
618
** Merge the two sorted lists p1 and p2 into a single list.
** Set *ppOut to the head of the new list.
*/
static void vdbeSorterMerge(
  const VdbeCursor *pCsr,         /* For pKeyInfo */
  SorterRecord *p1,               /* First list to merge */
  SorterRecord *p2,               /* Second list to merge */
  SorterRecord **ppOut            /* OUT: Head of merged list */

){
  SorterRecord *pFinal = 0;
  SorterRecord **pp = &pFinal;
  void *pVal2 = p2 ? p2->pVal : 0;

  while( p1 && p2 ){
    int res;
    vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res);

    if( res<=0 ){
      *pp = p1;
      pp = &p1->pNext;
      p1 = p1->pNext;
      pVal2 = 0;
    }else{
      *pp = p2;
       pp = &p2->pNext;
      p2 = p2->pNext;
      if( p2==0 ) break;
      pVal2 = p2->pVal;
    }
  }
  *pp = p1 ? p1 : p2;
  *ppOut = pFinal;
}

/*































































** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
** occurs.
*/
static int vdbeSorterSort(const VdbeCursor *pCsr){
  int i;
  SorterRecord **aSlot;
  SorterRecord *p;
  VdbeSorter *pSorter = pCsr->pSorter;









  aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
  if( !aSlot ){
    return SQLITE_NOMEM;
  }

  p = pSorter->pRecord;

  while( p ){
    SorterRecord *pNext = p->pNext;
    p->pNext = 0;
    for(i=0; aSlot[i]; i++){
      vdbeSorterMerge(pCsr, p, aSlot[i], &p);
      aSlot[i] = 0;
    }

    aSlot[i] = p;
    p = pNext;
  }

  p = 0;


  for(i=0; i<64; i++){
    vdbeSorterMerge(pCsr, p, aSlot[i], &p);


  }
  pSorter->pRecord = p;

  sqlite3_free(aSlot);
  return SQLITE_OK;
}

/*
** Initialize a file-writer object.
*/
static void fileWriterInit(
  sqlite3 *db,                    /* Database (for malloc) */







|
>







|
>


















>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>





|
<


>
>
>
>

>
>
>
>
|
|


|
|
>
|
<
|
<
<
|
<
>
|
|
|
|
|
>
>
|
|
>
>

|
|
|
|







544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648

649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667

668


669

670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
** Merge the two sorted lists p1 and p2 into a single list.
** Set *ppOut to the head of the new list.
*/
static void vdbeSorterMerge(
  const VdbeCursor *pCsr,         /* For pKeyInfo */
  SorterRecord *p1,               /* First list to merge */
  SorterRecord *p2,               /* Second list to merge */
  SorterRecord **ppOut,           /* OUT: Head of merged list */
  UnpackedRecord *pUnpacked       /* Space to hold an unpacked record */
){
  SorterRecord *pFinal = 0;
  SorterRecord **pp = &pFinal;
  void *pVal2 = p2 ? p2->pVal : 0;

  while( p1 && p2 ){
    int res;
    vdbeSorterCompare(pCsr, 0, p1->pVal, p1->nVal, pVal2, p2->nVal, &res,
                      pUnpacked);
    if( res<=0 ){
      *pp = p1;
      pp = &p1->pNext;
      p1 = p1->pNext;
      pVal2 = 0;
    }else{
      *pp = p2;
       pp = &p2->pNext;
      p2 = p2->pNext;
      if( p2==0 ) break;
      pVal2 = p2->pVal;
    }
  }
  *pp = p1 ? p1 : p2;
  *ppOut = pFinal;
}

/*
** Background sorting task
*/
typedef struct SortTask {
  SorterRecord *pList;          /* List of elements to be sorted */
  const VdbeCursor *pCsr;       /* Cursor.  Needed for pCur->pKeyInfo */
  UnpackedRecord *pUnpacked;    /* Space to hold an unpacked key */
  SorterRecord **apSlot;        /* Temp memory for the merge sort */
} SortTask;

/*
** Do a sort in a background thread
*/
void *vdbeSorterBackgroundSort(SortTask *pTask){
  SorterRecord *p = pTask->pList;
  SorterRecord **a = pTask->apSlot;
  int i;
  for(i=0; i<64; i++) a[i] = 0;
  while( p ){
    SorterRecord *pNext = p->pNext;
    p->pNext = 0;
    for(i=0; a[i]; i++){
      if( a[i]==0 ) break;
      vdbeSorterMerge(pTask->pCsr, a[i], p, &p, pTask->pUnpacked);
      a[i] = 0;
    }
    a[i] = p;
    p = pNext;
  }
  p = 0;
  for(i=0; i<64; i++){
    vdbeSorterMerge(pTask->pCsr, a[i], p, &p, pTask->pUnpacked);
  }
  pTask->pList = p;
  return p;
}

/*
** Divide a linked list of SorterRecord objects into two separate
** linked lists
*/
static void vdbeSorterDivideList(
  SorterRecord *pIn,       /* The list to be divided */
  SorterRecord **ppOut1,   /* Write the first list here */
  SorterRecord **ppOut2    /* Write the second list here */
){
  int i = 0;
  *ppOut1 = *ppOut2 = 0;
  while( pIn ){
    SorterRecord *pNext = pIn->pNext;
    pIn->pNext = 0;
    if( i & 1 ){
      *ppOut1 = pIn;
      ppOut1 = &pIn->pNext;
    }else{
      *ppOut2 = pIn;
      ppOut2 = &pIn->pNext;
    }
    i++;
    pIn = pNext;
  }
}

/*
** Sort the linked list of records headed at pCsr->pRecord. Return SQLITE_OK
** if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if an error
** occurs.
*/
static int vdbeSorterSort(const VdbeCursor *pCsr){
  int rc;

  SorterRecord *p;
  VdbeSorter *pSorter = pCsr->pSorter;
  char *pDummy = 0;
  int nByteA, nByteB;
  SortTask aTask[2];
  SQLiteThread *pThread;

  nByteA = 64*sizeof(SorterRecord*);
  nByteB = ROUND8(sizeof(UnpackedRecord));
  nByteB += sizeof(Mem)*(pCsr->pKeyInfo->nField+1);

  aTask[0].apSlot = (SorterRecord **)sqlite3MallocZero(2*(nByteA + nByteB));
  if( !aTask[0].apSlot ){
    return SQLITE_NOMEM;
  }
  aTask[0].pCsr = pCsr;
  aTask[0].pUnpacked = sqlite3VdbeAllocUnpackedRecord(pCsr->pKeyInfo,
                          (char*)&aTask[0].apSlot[64], nByteB, &pDummy);
  assert( pDummy==0 );

  aTask[1].apSlot = (nByteA+nByteB)+(char*)aTask[0].apSlot;


  aTask[1].pCsr = pCsr;

  aTask[1].pUnpacked = sqlite3VdbeAllocUnpackedRecord(pCsr->pKeyInfo,
                          (char*)&aTask[1].apSlot[64], nByteB, &pDummy);
  assert( pDummy==0 );

  vdbeSorterDivideList(pSorter->pRecord, &aTask[0].pList, &aTask[1].pList);
  rc = sqlite3ThreadCreate(&pThread, 
          (void*(*)(void*))vdbeSorterBackgroundSort, &aTask[0]);
  vdbeSorterBackgroundSort(&aTask[1]);
  if( rc==SQLITE_NOMEM ){
    vdbeSorterBackgroundSort(&aTask[0]);
  }else{
    rc = sqlite3ThreadJoin(pThread, &pDummy);
  }
  vdbeSorterMerge(pCsr, aTask[0].pList, aTask[1].pList, &pSorter->pRecord,
                  aTask[0].pUnpacked);
  sqlite3_free(aTask[0].apSlot);
  return rc;
}

/*
** Initialize a file-writer object.
*/
static void fileWriterInit(
  sqlite3 *db,                    /* Database (for malloc) */
715
716
717
718
719
720
721

722
723
724
725
726
727
728
  VdbeSorter *pSorter = pCsr->pSorter;
  FileWriter writer;

  memset(&writer, 0, sizeof(FileWriter));

  if( pSorter->nInMemory==0 ){
    assert( pSorter->pRecord==0 );

    return rc;
  }

  rc = vdbeSorterSort(pCsr);

  /* If the first temporary PMA file has not been opened, open it now. */
  if( rc==SQLITE_OK && pSorter->pTemp1==0 ){







>







790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
  VdbeSorter *pSorter = pCsr->pSorter;
  FileWriter writer;

  memset(&writer, 0, sizeof(FileWriter));

  if( pSorter->nInMemory==0 ){
    assert( pSorter->pRecord==0 );
    assert( pSorter->nRecord==0 );
    return rc;
  }

  rc = vdbeSorterSort(pCsr);

  /* If the first temporary PMA file has not been opened, open it now. */
  if( rc==SQLITE_OK && pSorter->pTemp1==0 ){
741
742
743
744
745
746
747
748

749
750
751
752
753
754
755
    fileWriterWriteVarint(&writer, pSorter->nInMemory);
    for(p=pSorter->pRecord; p; p=pNext){
      pNext = p->pNext;
      fileWriterWriteVarint(&writer, p->nVal);
      fileWriterWrite(&writer, p->pVal, p->nVal);
      sqlite3DbFree(db, p);
    }
    pSorter->pRecord = p;

    rc = fileWriterFinish(db, &writer, &pSorter->iWriteOff);
  }

  return rc;
}

/*







|
>







817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
    fileWriterWriteVarint(&writer, pSorter->nInMemory);
    for(p=pSorter->pRecord; p; p=pNext){
      pNext = p->pNext;
      fileWriterWriteVarint(&writer, p->nVal);
      fileWriterWrite(&writer, p->pVal, p->nVal);
      sqlite3DbFree(db, p);
    }
    pSorter->pRecord = 0;
    pSorter->nRecord = 0;
    rc = fileWriterFinish(db, &writer, &pSorter->iWriteOff);
  }

  return rc;
}

/*
772
773
774
775
776
777
778

779
780
781
782
783
784
785
    rc = SQLITE_NOMEM;
  }else{
    pNew->pVal = (void *)&pNew[1];
    memcpy(pNew->pVal, pVal->z, pVal->n);
    pNew->nVal = pVal->n;
    pNew->pNext = pSorter->pRecord;
    pSorter->pRecord = pNew;

  }

  /* See if the contents of the sorter should now be written out. They
  ** are written out when either of the following are true:
  **
  **   * The total memory allocated for the in-memory list is greater 
  **     than (page-size * cache-size), or







>







849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
    rc = SQLITE_NOMEM;
  }else{
    pNew->pVal = (void *)&pNew[1];
    memcpy(pNew->pVal, pVal->z, pVal->n);
    pNew->nVal = pVal->n;
    pNew->pNext = pSorter->pRecord;
    pSorter->pRecord = pNew;
    pSorter->nRecord++;
  }

  /* See if the contents of the sorter should now be written out. They
  ** are written out when either of the following are true:
  **
  **   * The total memory allocated for the in-memory list is greater 
  **     than (page-size * cache-size), or
961
962
963
964
965
966
967

968
969
970
971
972
973
974
      rc = vdbeSorterDoCompare(pCsr, i);
    }

    *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
  }else{
    SorterRecord *pFree = pSorter->pRecord;
    pSorter->pRecord = pFree->pNext;

    pFree->pNext = 0;
    vdbeSorterRecordFree(db, pFree);
    *pbEof = !pSorter->pRecord;
    rc = SQLITE_OK;
  }
  return rc;
}







>







1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
      rc = vdbeSorterDoCompare(pCsr, i);
    }

    *pbEof = (pSorter->aIter[pSorter->aTree[1]].pFile==0);
  }else{
    SorterRecord *pFree = pSorter->pRecord;
    pSorter->pRecord = pFree->pNext;
    pSorter->nRecord--;
    pFree->pNext = 0;
    vdbeSorterRecordFree(db, pFree);
    *pbEof = !pSorter->pRecord;
    rc = SQLITE_OK;
  }
  return rc;
}
1027
1028
1029
1030
1031
1032
1033
1034

1035
1036
1037
1038
  Mem *pVal,                      /* Value to compare to current sorter key */
  int *pRes                       /* OUT: Result of comparison */
){
  VdbeSorter *pSorter = pCsr->pSorter;
  void *pKey; int nKey;           /* Sorter key to compare pVal with */

  pKey = vdbeSorterRowkey(pSorter, &nKey);
  vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes);

  return SQLITE_OK;
}

#endif /* #ifndef SQLITE_OMIT_MERGE_SORT */







|
>




1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
  Mem *pVal,                      /* Value to compare to current sorter key */
  int *pRes                       /* OUT: Result of comparison */
){
  VdbeSorter *pSorter = pCsr->pSorter;
  void *pKey; int nKey;           /* Sorter key to compare pVal with */

  pKey = vdbeSorterRowkey(pSorter, &nKey);
  vdbeSorterCompare(pCsr, 1, pVal->z, pVal->n, pKey, nKey, pRes,
                    pSorter->pUnpacked);
  return SQLITE_OK;
}

#endif /* #ifndef SQLITE_OMIT_MERGE_SORT */