/ Check-in [11dd05e5]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 | SQL 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
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: 555fc07e 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: 11dd05e5 user: drh tags: threads-sort-ex1
11:24
Update the threads branch to include all the latest trunk changes. check-in: f4125771 user: drh tags: threads
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/vdbesort.c.

101
102
103
104
105
106
107

108
109
110
111
112
113
114
...
383
384
385
386
387
388
389
390

391
392
393
394
395
396
397

398
399
400
401
402
403
404
...
441
442
443
444
445
446
447
448
449
450

451
452
453
454
455
456
457
...
543
544
545
546
547
548
549
550

551
552
553
554
555
556
557
558

559
560
561
562
563
564
565
...
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
...
715
716
717
718
719
720
721

722
723
724
725
726
727
728
...
741
742
743
744
745
746
747
748

749
750
751
752
753
754
755
...
772
773
774
775
776
777
778

779
780
781
782
783
784
785
...
961
962
963
964
965
966
967

968
969
970
971
972
973
974
....
1027
1028
1029
1030
1031
1032
1033
1034

1035
1036
1037
1038
  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.
*/
................................................................................
** 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++){
................................................................................

  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;
    }
  }
................................................................................
** 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;
................................................................................
      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) */
................................................................................
  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 ){
................................................................................
    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;
}

/*
................................................................................
    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
................................................................................
      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;
}
................................................................................
  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 */







>







 







|
>


<
<



>







 







<

|
>







 







|
>







|
>







 









|
<
<

>
>
|
|
|
|
<

>
|
<
>
|
<
<
>
>
|
>



|
<
>
>
|

|


<


<
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|







 







>







 







|
>







 







>







 







>







 







|
>




101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
...
384
385
386
387
388
389
390
391
392
393
394


395
396
397
398
399
400
401
402
403
404
405
...
442
443
444
445
446
447
448

449
450
451
452
453
454
455
456
457
458
...
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
...
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
...
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
...
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
...
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
....
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
....
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
  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.
*/
................................................................................
** 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++){
................................................................................

  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;
    }
  }
................................................................................
** 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;
................................................................................
      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) */
................................................................................
  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 ){
................................................................................
    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;
}

/*
................................................................................
    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
................................................................................
      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;
}
................................................................................
  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 */