[Zodb-checkins] CVS: Zope/lib/python/BTrees - SetOpTemplate.c:1.16

[Tim Peters]

Update of /cvs-repository/Zope/lib/python/BTrees
In directory cvs.zope.org:/tmp/cvs-serv14639

Modified Files:
	SetOpTemplate.c 
Log Message:
multiunion():  For an input that's IIBucket-based (IIBucket and IISet),
this now copies the keys into the work area in one gulp via memcpy,
instead of iterating over them one at a time.  Yields a nice speedup when
it applies (and it usually should apply!).


=== Zope/lib/python/BTrees/SetOpTemplate.c 1.15 => 1.16 ===
        set.  At this point, we ignore the possibility of duplicates. */
     for (i = 0; i < n; ++i) {
-        SetIteration setiter = {0, 0, 0};
-        int merge;  /* dummy needed for initSetIteration */
-
         set = PySequence_GetItem(seq, i);
         if (set == NULL)
             goto Error;
 
-        /* XXX TODO: If set is a bucket, do a straight resize+memcpy instead.
-        */
-        if (initSetIteration(&setiter, set, 1, &merge) < 0)
-            goto Error;
-        if (setiter.next(&setiter) < 0)
-            goto Error;
-        while (setiter.position >= 0) {
-            if (result->len >= result->size && Bucket_grow(result, -1, 1) < 0)
+        /* If set is a bucket, do a straight resize + memcpy. */
+        if (set->ob_type == (PyTypeObject*)&SetType ||
+            set->ob_type == (PyTypeObject*)&BucketType) {
+            const int setsize = SIZED(set)->len;
+            int size_desired = result->len + setsize;
+            /* If there are more to come, overallocate by 25% (arbitrary). */
+            if (i < n-1)
+                size_desired += size_desired >> 2;
+            if (size_desired && size_desired > result->size) {
+                if (Bucket_grow(result, size_desired, 1) < 0)
+                    goto Error;
+            }
+            memcpy(result->keys + result->len,
+                   BUCKET(set)->keys,
+                   setsize * sizeof(KEY_TYPE));
+            result->len += setsize;
+        }
+        else {
+            /* No cheap way:  iterate over set's elements one at a time. */
+            SetIteration setiter = {0, 0, 0};
+            int merge;  /* dummy needed for initSetIteration */
+            
+            if (initSetIteration(&setiter, set, 1, &merge) < 0)
                 goto Error;
-            COPY_KEY(result->keys[result->len], setiter.key);
-            ++result->len;
-            /* We know the key is an int, so no need to incref it. */
             if (setiter.next(&setiter) < 0)
                 goto Error;
+            while (setiter.position >= 0) {
+                if (result->len >= result->size && Bucket_grow(result, -1, 1) < 0)
+                    goto Error;
+                COPY_KEY(result->keys[result->len], setiter.key);
+                ++result->len;
+                /* We know the key is an int, so no need to incref it. */
+                if (setiter.next(&setiter) < 0)
+                    goto Error;
+            }
         }
         Py_DECREF(set);
         set = NULL;