Merge lp:~epics-core/epics-base/bigdb into lp:~epics-core/epics-base/3.16

[mdavidsaver]

A couple of weeks ago I made a semi-intentional test of what happens to an IOC with >100k records. It works quite well, if you have the patience to wait for it to start up. Some profiling found two hot spots, both list insertion sorts, in dbCreateRecord() and addToList(). trans() in macCore.c is a distant third.

The loop in addToList() is written in such a way that the common case (all PHAS==0) always traverses the entire list. I change this the common case simply appends, and the worst case is unchanged.

dbCreateRecord() is harder to fix while still maintaining the sorting*. I settled on re-sorting once per call to dbReadCOM(), which works except for dbReadTemplate() with lots of little templates.

* It would be even better to sort once in iocInit(), or not at all, but I wasn't sure if anything depends on the ordering.

[Andrew Johnson (anj)]

Interesting.

Please adjust or remove the comment at dbStaticLib.c:1415. I can't immediately think of a reason why records still need to be sorted; that particular comment in dbCreateRecord() dates back to when dbStaticLib.c was first added to CVS in 1993 (commit #905). There was already a hash table which was used for name lookups in that version, so it wasn't to speed up name searches. It was most likely because back in the days of binary database files and the curses-based dct (database configuration tool), record names for editing were presented to the user in a list, and it would have been very unfriendly to not have sorted it first. Have you tried removing the sort completely?

The new ellSort.c file should have a copyright/license header. I don't recognize any of the chiark website's example C code in it, so I'm guessing you wrote this yourself from scratch just using the algorithm and we don't need to import their copyright notice or license text at all.

[lp:~epics-core/epics-base/bigdb]

12741. By mdavidsaver on 2016-04-27

fixup comments

[mdavidsaver (mdavidsaver)]

> Please adjust or remove the comment at dbStaticLib.c:1415.
> The new ellSort.c file should have a copyright/license header.

Done

> I don't recognize any of the chiark website's example C code
> in it, so I'm guessing you wrote this yourself from scratch

Correct. I just want to give due credit. I went looking for the best way to sort linked lists, and there was a well thought out answer waiting.

> Have you tried removing the sort completely?

Yup. Works fine. I couldn't find anything in Base which depends on the ordering.

> ... dates back to when dbStaticLib.c was first added to CVS in 1993 ...

I know. There was dust, and spiders.

[Ralph Lange (ralph-lange)]

Looks good (with two minor issues in comments).

review: Approve

[lp:~epics-core/epics-base/bigdb]

12742. By mdavidsaver on 2016-04-27

ellSort: comments and redundant asserts

[Andrew Johnson (anj)]

dbCreateAlias() also needs to be updated, it still does an insertion sort.

If we remove the sort completely dbRenameRecord() would also need changes, although it could be removed completely from 3.15 or 3.16 as it is only useful as part of the old dbStaticHost library by Database Configuration Tools which these branches don't build any more.

review: Needs Fixing

[Ralph Lange (ralph-lange)]

I will take care of the remaining things and prepare a merge proposal for the 3.15 branch, including removal of dbRenameRecord() - I had been wondering what it was good for a couple of times.

A possible backport to 3.14 would have to add the changes to dbRenameRecord().

[mdavidsaver (mdavidsaver)]

Thank you Ralph. I'm trying to spend what little dev. time I have atm. on tests for the link support code.

[Ralph Lange (ralph-lange)]

This merge request has been superseded by its 3.15 rebase,
https://code.launchpad.net/~epics-core/epics-base/bigdb-3.15

review: Needs Resubmitting

Unmerged revisions

12742. By mdavidsaver on 2016-04-27

ellSort: comments and redundant asserts

12741. By mdavidsaver on 2016-04-27

fixup comments

12740. By mdavidsaver on 2016-04-26

test ellSortStable

12739. By mdavidsaver on 2016-04-26

dbCreateRecord use ellSortStable()

sort records once per dbLoadCOM()

12738. By mdavidsaver on 2016-04-26

ellSort

12737. By mdavidsaver on 2016-04-26

dbScan: optimize addToList

Insert from back to maintain ~same order.
Avoid iterating entire list each time
in the common case where all PHAS==0

12736. By mdavidsaver on 2016-04-26

whitespace

=== modified file 'src/ioc/db/dbScan.c'
--- src/ioc/db/dbScan.c	2015-09-07 04:15:21 +0000
+++ src/ioc/db/dbScan.c	2016-04-27 12:02:50 +0000
@@ -989,9 +989,9 @@
         pse->precord = precord;
     }
     pse->pscan_list = psl;
-    ptemp = (scan_element *)ellFirst(&psl->list);
+    ptemp = (scan_element *)ellLast(&psl->list);
     while (ptemp) {
-        if (ptemp->precord->phas > precord->phas) {
+        if (ptemp->precord->phas <= precord->phas) {
             ellInsert(&psl->list, ellPrevious(&ptemp->node), &pse->node);
             break;
         }

=== modified file 'src/ioc/dbStatic/dbBase.h'
--- src/ioc/dbStatic/dbBase.h	2015-02-03 06:38:23 +0000
+++ src/ioc/dbStatic/dbBase.h	2016-04-27 12:02:50 +0000
@@ -134,25 +134,25 @@
 }dbVariableDef;
 
 typedef struct dbRecordType {
-	ELLNODE		node;
-	ELLLIST		attributeList;	/*LIST head of attributes*/
-	ELLLIST		recList;	/*LIST head of sorted dbRecordNodes*/
-	ELLLIST		devList;	/*List of associated device support*/
-	ELLLIST		cdefList;	/*LIST of Cdef text items*/
-	char		*name;
-	short		no_fields;	/* number of fields defined	*/
-	short		no_prompt;	/* number of fields to configure*/
-	short		no_links;	/* number of links		*/
-	short		no_aliases;	/* number of aliases in recList */
-	short		*link_ind;	/* addr of array of ind in papFldDes*/
-	char		**papsortFldName;/* ptr to array of ptr to fld names*/
-	short		*sortFldInd;	/* addr of array of ind in papFldDes*/
-	dbFldDes	*pvalFldDes;	/*pointer dbFldDes for VAL field*/
-	short		indvalFlddes;	/*ind in papFldDes*/
-	dbFldDes 	**papFldDes;	/* ptr to array of ptr to fldDes*/
-	/*The following are only available on run time system*/
-	struct	rset	*prset;
-	int		rec_size;	/*record size in bytes          */
+    ELLNODE		node;
+    ELLLIST		attributeList;	/*LIST head of attributes*/
+    ELLLIST		recList;	/*LIST head of sorted dbRecordNodes*/
+    ELLLIST		devList;	/*List of associated device support*/
+    ELLLIST		cdefList;	/*LIST of Cdef text items*/
+    char		*name;
+    short		no_fields;	/* number of fields defined	*/
+    short		no_prompt;	/* number of fields to configure*/
+    short		no_links;	/* number of links		*/
+    short		no_aliases;	/* number of aliases in recList */
+    short		*link_ind;	/* addr of array of ind in papFldDes*/
+    char		**papsortFldName;/* ptr to array of ptr to fld names*/
+    short		*sortFldInd;	/* addr of array of ind in papFldDes*/
+    dbFldDes	*pvalFldDes;	/*pointer dbFldDes for VAL field*/
+    short		indvalFlddes;	/*ind in papFldDes*/
+    dbFldDes 	**papFldDes;	/* ptr to array of ptr to fldDes*/
+    /*The following are only available on run time system*/
+    struct	rset	*prset;
+    int		rec_size;	/*record size in bytes          */
 }dbRecordType;
 
 struct dbPvd;           /* Contents private to dbPvdLib code */

=== modified file 'src/ioc/dbStatic/dbLexRoutines.c'
--- src/ioc/dbStatic/dbLexRoutines.c	2016-02-27 00:16:26 +0000
+++ src/ioc/dbStatic/dbLexRoutines.c	2016-04-27 12:02:50 +0000
@@ -195,7 +195,16 @@
 	free((void *)pinputFileNow);
     }
 }
-

+
+static
+int cmp_dbRecordNode(const ELLNODE *lhs, const ELLNODE *rhs)
+{
+    dbRecordNode *LHS = (dbRecordNode*)lhs,
+                 *RHS = (dbRecordNode*)rhs;
+
+    return strcmp(LHS->recordname, RHS->recordname);
+}
+
 static long dbReadCOM(DBBASE **ppdbbase,const char *filename, FILE *fp,
 	const char *path,const char *substitutions)
 {
@@ -295,6 +304,15 @@
 	dbFinishEntry(pdbEntry);
     }
 cleanup:
+    {
+        ELLNODE *cur;
+        for(cur = ellFirst(&pdbbase->recordTypeList); cur; cur=ellNext(cur))
+        {
+            dbRecordType *rtype = CONTAINER(cur, dbRecordType, node);
+
+            ellSortStable(&rtype->recList, &cmp_dbRecordNode);
+        }
+    }
     if(macHandle) macDeleteHandle(macHandle);
     macHandle = NULL;
     if(mac_input_buffer) free((void *)mac_input_buffer);

=== modified file 'src/ioc/dbStatic/dbStaticLib.c'
--- src/ioc/dbStatic/dbStaticLib.c	2016-03-30 17:39:36 +0000
+++ src/ioc/dbStatic/dbStaticLib.c	2016-04-27 12:02:50 +0000
@@ -1397,7 +1397,7 @@
     /*Get size of NAME field*/
     pdbFldDes = precordType->papFldDes[0];
     if(!pdbFldDes || (strcmp(pdbFldDes->name,"NAME")!=0))
-	return(S_dbLib_nameLength);
+        return(S_dbLib_nameLength);
     if((int)strlen(precordName)>=pdbFldDes->size) return(S_dbLib_nameLength);
     /* clear callers entry */
     zeroDbentry(pdbentry);
@@ -1412,18 +1412,7 @@
     if((status = dbAllocRecord(pdbentry,precordName))) return(status);
     pNewRecNode->recordname = dbRecordName(pdbentry);
     ellInit(&pNewRecNode->infoList);
-    /* install record node in list in sorted postion */
-    status = dbFirstRecord(pdbentry);
-    while(status==0) {
-        if(strcmp(precordName,dbGetRecordName(pdbentry)) < 0) break;
-        status = dbNextRecord(pdbentry);
-    }
-    if(status==0) {
-        precnode = pdbentry->precnode;
-	ellInsert(preclist,ellPrevious(&precnode->node),&pNewRecNode->node);
-    } else {
-        ellAdd(preclist,&pNewRecNode->node);
-    }
+    ellAdd(preclist, &pNewRecNode->node);
     pdbentry->precnode = pNewRecNode;
     ppvd = dbPvdAdd(pdbentry->pdbbase,precordType,pNewRecNode);
     if(!ppvd) {errMessage(-1,"Logic Err: Could not add to PVD");return(-1);}

=== modified file 'src/libCom/ellLib/Makefile'
--- src/libCom/ellLib/Makefile	2011-02-25 21:39:44 +0000
+++ src/libCom/ellLib/Makefile	2016-04-27 12:02:50 +0000
@@ -10,3 +10,4 @@
 SRC_DIRS += $(LIBCOM)/ellLib
 INC += ellLib.h
 Com_SRCS += ellLib.c
+Com_SRCS += ellSort.c

=== modified file 'src/libCom/ellLib/ellLib.h'
--- src/libCom/ellLib/ellLib.h	2012-04-27 17:21:57 +0000
+++ src/libCom/ellLib/ellLib.h	2016-04-27 12:02:50 +0000
@@ -58,6 +58,8 @@
 epicsShareFunc ELLNODE * ellNth (ELLLIST *pList, int nodeNum);
 epicsShareFunc ELLNODE * ellNStep (ELLNODE *pNode, int nStep);
 epicsShareFunc int  ellFind (ELLLIST *pList, ELLNODE *pNode);
+typedef int (*pListCmp)(ELLNODE* A, ELLNODE* B);
+epicsShareFunc void ellSortStable(ELLLIST *pList, pListCmp);
 epicsShareFunc void ellFree2 (ELLLIST *pList, FREEFUNC freeFunc);
 epicsShareFunc void ellVerify (ELLLIST *pList);
 

=== added file 'src/libCom/ellLib/ellSort.c'
--- src/libCom/ellLib/ellSort.c	1970-01-01 00:00:00 +0000
+++ src/libCom/ellLib/ellSort.c	2016-04-27 12:02:50 +0000
@@ -0,0 +1,83 @@
+/*************************************************************************\
+* Copyright (c) 2014 Brookhaven Science Assoc., as Operator of Argonne
+*     National Laboratory.
+* Copyright (c) 2016 Michael Davidsaver
+* EPICS BASE is distributed subject to a Software License Agreement found
+* in file LICENSE that is included with this distribution.
+\*************************************************************************/
+
+/*
+ * Use of mergesort algorithm based on analysis by
+ * http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
+ */
+#include <stdlib.h>
+
+#define epicsExportSharedSymbols
+#include "epicsAssert.h"
+#include "ellLib.h"
+
+static void ellMoveN(ELLLIST* pTo, ELLLIST* pFrom, int count )
+{
+    for(;count && ellCount(pFrom); count--) {
+        ELLNODE *node = ellGet(pFrom);
+        ellAdd(pTo, node);
+    }
+}
+
+/* Stable (MergeSort) to given list.
+ * The comparison function cmp(A,B) is expected
+ * to return -1 for A<B, 0 for A==B, and 1 for A>B.
+ */
+void ellSortStable(ELLLIST *pList, pListCmp cmp)
+{
+    ELLLIST INP, P, Q;
+    size_t insize = 1; /* initial sub-list size */
+    if(ellCount(pList)<=1)
+        return;
+
+    ellInit(&INP);
+    ellInit(&P);
+    ellInit(&Q);
+
+    /* Process is to iteratively sort
+     * a sequence of sub-lists of size 'insize'
+     */
+
+    while(insize < ellCount(pList)) {
+
+        assert(ellCount(&INP)==0);
+
+        /* shift previous results to inputs */
+        ellConcat(&INP, pList);
+
+        while(ellCount(&INP))
+        {
+            ELLNODE *p, *q;
+
+            /* Pull out the next pair of sub-lists */
+            ellMoveN(&Q, &INP, insize);
+            ellMoveN(&P, &INP, insize);
+
+            /* merge these sub-lists */
+            while((p=ellFirst(&P)) && (q=ellFirst(&Q)))
+            {
+                if((*cmp)(p,q) < 0) {
+                    ellAdd(pList, ellGet(&P));
+                } else {
+                    ellAdd(pList, ellGet(&Q));
+                }
+            }
+
+            /* concatenate any remaining to result */
+            if(ellFirst(&P))
+                ellConcat(pList, &P);
+            else if(ellFirst(&Q))
+                ellConcat(pList, &Q);
+
+            assert(!ellFirst(&P) && !ellFirst(&Q));
+        }
+
+        insize *= 2;
+    }
+
+}

=== modified file 'src/libCom/test/epicsEllTest.c'
--- src/libCom/test/epicsEllTest.c	2009-08-28 18:34:38 +0000
+++ src/libCom/test/epicsEllTest.c	2016-04-27 12:02:50 +0000
@@ -1,4 +1,5 @@
 /*************************************************************************\
+* Copyright (c) 2016 Michael Davidsaver
 * Copyright (c) 2009 UChicago Argonne LLC, as Operator of Argonne
 *     National Laboratory.
 * Copyright (c) 2002 The Regents of the University of California, as
@@ -11,6 +12,7 @@
 #include <stdlib.h>
 
 #include "ellLib.h"
+#include "dbDefs.h"
 #include "epicsUnitTest.h"
 #include "testMain.h"
 
@@ -20,15 +22,13 @@
     int num;
 };
 
-MAIN(epicsEllTest)
+static void testList(void)
 {
     ELLLIST list1;
     ELLLIST list2 = ELLLIST_INIT;
     int i1 = 1;
     struct myItem *pitem, *pfirst, *pick;
 
-    testPlan(70);
-
     list1.count = 27;
     list1.node.next = (ELLNODE *) 0x01010101;
     list1.node.previous = (ELLNODE *) 0x10101010;
@@ -192,6 +192,77 @@
 
     ellFree2(&list1, free);
     testOk1(ellCount(&list1) == 0);
+}
+
+typedef struct { int A, B; } input_t;
+
+static int myItemCmp(ELLNODE *a, ELLNODE *b)
+{
+    struct myItem *A = CONTAINER(a, struct myItem, node),
+                  *B = CONTAINER(b, struct myItem, node);
+
+    if     (A->num < B->num)   return -1;
+    else if(A->num > B->num)   return 1;
+    else if(A->list < B->list) return -1;
+    else if(A->list > B->list) return 1;
+    else                       return 0;
+}
+
+static const input_t input[] = {
+    {-4, 0},
+    {-5, 0},
+    {0,0},
+    {50,0},
+    {0,1},
+    {5,0},
+    {5,1}
+};
+
+static
+void testSort(const input_t *inp, size_t ninp)
+{
+    unsigned i;
+    ELLLIST list = ELLLIST_INIT;
+    struct myItem *alloc = calloc(ninp, sizeof(*alloc));
+
+    if(!alloc) testAbort("testSort allocation fails");
+
+    for(i=0; i<ninp; i++) {
+        struct myItem *it = &alloc[i];
+
+        it->num = inp[i].A;
+        it->list= inp[i].B;
+
+        ellAdd(&list, &it->node);
+    }
+
+    ellSortStable(&list, &myItemCmp);
+
+    testOk(ellCount(&list)==ninp, "output length %u == %u", (unsigned)ellCount(&list), (unsigned)ninp);
+    if(ellCount(&list)==0) {
+        testSkip(ninp-1, "all items lost");
+    }
+
+    {
+        struct myItem *prev = CONTAINER(ellFirst(&list), struct myItem, node),
+                      *next;
+
+        for(next = CONTAINER(ellNext(&prev->node), struct myItem, node);
+            next;
+            prev = next, next = CONTAINER(ellNext(&next->node), struct myItem, node))
+        {
+            int cond = (prev->num<next->num) || (prev->num==next->num && prev->list<next->list);
+            testOk(cond, "%d:%d < %d:%d", prev->num, prev->list, next->num, next->list);
+        }
+    }
+}
+
+MAIN(epicsEllTest)
+{
+    testPlan(77);
+
+    testList();
+    testSort(input, NELEMENTS(input));
 
     return testDone();
 }