[patch] avoid dynamic alloc in vdbeSorterSort(...)

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

[patch] avoid dynamic alloc in vdbeSorterSort(...)

Dominique Pellé
Hi

Below is a patch which avoids a dynamic
allocation in vdbeSorterSort(...), using a local
stack array instead (faster and smaller code).
I assume that a local array of 64 pointers is small
enough to be in the stack.

Is this worth merging?

$ fossil diff  src/vdbesort.c
Index: src/vdbesort.c
==================================================================
--- src/vdbesort.c
+++ src/vdbesort.c
@@ -1394,25 +1394,20 @@
 ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if
 ** an error occurs.
 */
 static int vdbeSorterSort(SortSubtask *pTask, SorterList *pList){
   int i;
-  SorterRecord **aSlot;
+  SorterRecord *aSlot[64] = { 0 };
   SorterRecord *p;
   int rc;

   rc = vdbeSortAllocUnpacked(pTask);
   if( rc!=SQLITE_OK ) return rc;

   p = pList->pList;
   pTask->xCompare = vdbeSorterGetCompare(pTask->pSorter);

-  aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
-  if( !aSlot ){
-    return SQLITE_NOMEM_BKPT;
-  }
-
   while( p ){
     SorterRecord *pNext;
     if( pList->aMemory ){
       if( (u8*)p==pList->aMemory ){
         pNext = 0;
@@ -1438,11 +1433,10 @@
     if( aSlot[i]==0 ) continue;
     p = p ? vdbeSorterMerge(pTask, p, aSlot[i]) : aSlot[i];
   }
   pList->pList = p;

-  sqlite3_free(aSlot);
   assert( pTask->pUnpacked->errCode==SQLITE_OK
        || pTask->pUnpacked->errCode==SQLITE_NOMEM
   );
   return pTask->pUnpacked->errCode;
 }

Regards
Dominique
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [patch] avoid dynamic alloc in vdbeSorterSort(...)

Mateusz Wajchęprzełóż
What about sqlite3StackAllocZero and SQLITE_USE_ALLOCA?

pon., 7 paź 2019 o 20:51 Dominique Pellé <[hidden email]>
napisał(a):

> Hi
>
> Below is a patch which avoids a dynamic
> allocation in vdbeSorterSort(...), using a local
> stack array instead (faster and smaller code).
> I assume that a local array of 64 pointers is small
> enough to be in the stack.
>
> Is this worth merging?
>
> $ fossil diff  src/vdbesort.c
> Index: src/vdbesort.c
> ==================================================================
> --- src/vdbesort.c
> +++ src/vdbesort.c
> @@ -1394,25 +1394,20 @@
>  ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if
>  ** an error occurs.
>  */
>  static int vdbeSorterSort(SortSubtask *pTask, SorterList *pList){
>    int i;
> -  SorterRecord **aSlot;
> +  SorterRecord *aSlot[64] = { 0 };
>    SorterRecord *p;
>    int rc;
>
>    rc = vdbeSortAllocUnpacked(pTask);
>    if( rc!=SQLITE_OK ) return rc;
>
>    p = pList->pList;
>    pTask->xCompare = vdbeSorterGetCompare(pTask->pSorter);
>
> -  aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
> -  if( !aSlot ){
> -    return SQLITE_NOMEM_BKPT;
> -  }
> -
>    while( p ){
>      SorterRecord *pNext;
>      if( pList->aMemory ){
>        if( (u8*)p==pList->aMemory ){
>          pNext = 0;
> @@ -1438,11 +1433,10 @@
>      if( aSlot[i]==0 ) continue;
>      p = p ? vdbeSorterMerge(pTask, p, aSlot[i]) : aSlot[i];
>    }
>    pList->pList = p;
>
> -  sqlite3_free(aSlot);
>    assert( pTask->pUnpacked->errCode==SQLITE_OK
>         || pTask->pUnpacked->errCode==SQLITE_NOMEM
>    );
>    return pTask->pUnpacked->errCode;
>  }
>
> Regards
> Dominique
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [patch] avoid dynamic alloc in vdbeSorterSort(...)

Dominique Pellé
Here the allocated size is fixed (always 64 pointers), so alloca does
not seem needed.

I wonder how many other functions could avoid dynamic allocation
like this one (either with a stack array or alloca).

Regards
Dominique

On Mon, Oct 7, 2019 at 10:26 PM Mateusz Wajchęprzełóż
<[hidden email]> wrote:

>
> What about sqlite3StackAllocZero and SQLITE_USE_ALLOCA?
>
> pon., 7 paź 2019 o 20:51 Dominique Pellé <[hidden email]>
> napisał(a):
>
> > Hi
> >
> > Below is a patch which avoids a dynamic
> > allocation in vdbeSorterSort(...), using a local
> > stack array instead (faster and smaller code).
> > I assume that a local array of 64 pointers is small
> > enough to be in the stack.
> >
> > Is this worth merging?
> >
> > $ fossil diff  src/vdbesort.c
> > Index: src/vdbesort.c
> > ==================================================================
> > --- src/vdbesort.c
> > +++ src/vdbesort.c
> > @@ -1394,25 +1394,20 @@
> >  ** SQLITE_OK if successful, or an SQLite error code (i.e. SQLITE_NOMEM) if
> >  ** an error occurs.
> >  */
> >  static int vdbeSorterSort(SortSubtask *pTask, SorterList *pList){
> >    int i;
> > -  SorterRecord **aSlot;
> > +  SorterRecord *aSlot[64] = { 0 };
> >    SorterRecord *p;
> >    int rc;
> >
> >    rc = vdbeSortAllocUnpacked(pTask);
> >    if( rc!=SQLITE_OK ) return rc;
> >
> >    p = pList->pList;
> >    pTask->xCompare = vdbeSorterGetCompare(pTask->pSorter);
> >
> > -  aSlot = (SorterRecord **)sqlite3MallocZero(64 * sizeof(SorterRecord *));
> > -  if( !aSlot ){
> > -    return SQLITE_NOMEM_BKPT;
> > -  }
> > -
> >    while( p ){
> >      SorterRecord *pNext;
> >      if( pList->aMemory ){
> >        if( (u8*)p==pList->aMemory ){
> >          pNext = 0;
> > @@ -1438,11 +1433,10 @@
> >      if( aSlot[i]==0 ) continue;
> >      p = p ? vdbeSorterMerge(pTask, p, aSlot[i]) : aSlot[i];
> >    }
> >    pList->pList = p;
> >
> > -  sqlite3_free(aSlot);
> >    assert( pTask->pUnpacked->errCode==SQLITE_OK
> >         || pTask->pUnpacked->errCode==SQLITE_NOMEM
> >    );
> >    return pTask->pUnpacked->errCode;
> >  }
> >
> > Regards
> > Dominique
> > _______________________________________________
> > sqlite-users mailing list
> > [hidden email]
> > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> >
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [patch] avoid dynamic alloc in vdbeSorterSort(...)

Keith Medcalf

On Monday, 7 October, 2019 14:58, Dominique Pellé <[hidden email]> wrote:

>Here the allocated size is fixed (always 64 pointers), so alloca does
>not seem needed.

>I wonder how many other functions could avoid dynamic allocation
>like this one (either with a stack array or alloca).

Probably a lot.  I would note that it probably does not allocate on the stack by default because SQLite3 is intended to be cross-platform.  While many Operating Systems and Platforms may allow for lots of stack (virtually unlimited for modern flat address space Operating Systems running on x86_64 hardware), this is not necessarily the case for all Operating Systems or platforms in which the per-thread or per-process stack may be quite limited.

For example, in a single-thread process on a "flat virtual address space" machine, the stack theoretically extends from the end of the last code segment all the way up to the bottom of the heap (the heap grows down and the stack grows up).  However, as soon as you allow multiple threads in that process, you now have an arbitrary constrained stack, since the threads must each now be allocated a specific address space range for that threads stack.

If the memory model is not "flat", then the problem won't exist because the additional thread will merely be allocated a different "selector" for its stack.  However, not all machines treat segments as selectors, so there may very well still be constraints (ie, consider the old 16-bit addressing mode the segments/selectors were really just paragraph addresses in a flat address space, not true selectors).

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.



_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [patch] avoid dynamic alloc in vdbeSorterSort(...)

Dominique Pellé
Keith Medcalf <[hidden email]> wrote:

>
> On Monday, 7 October, 2019 14:58, Dominique Pellé <
> [hidden email]> wrote:
>
> >Here the allocated size is fixed (always 64 pointers), so alloca does
> >not seem needed.
>
> >I wonder how many other functions could avoid dynamic allocation
> >like this one (either with a stack array or alloca).
>
> Probably a lot. [...]


I don't think that there are a lot of other such avoidable malloc.
I searched the source code and could not find any (I may have
missed some of course).

For the records, I see that the proposed change has been merged
(slightly modified):
https://www.sqlite.org/src/info/5d76dbc5b0584c15

Regards
Dominique
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users