Changeset 17

Timestamp:

01/17/09 19:04:12 (3 years ago)

Author:

dsimcha

Message:

Optimize TempAlloc?. Fix a few minor bugs.

Files:

• trunk/alloc.d (modified) (24 diffs)
• trunk/cor.d (modified) (1 diff)
• trunk/distrib.d (modified) (2 diffs)
• trunk/random.d (modified) (1 diff)
• trunk/sort.d (modified) (12 diffs)
• trunk/stats.d (modified) (1 diff)
• trunk/summary.d (modified) (6 diffs)
• trunk/tests.d (modified) (1 diff)

trunk/alloc.d

@@ -2 +2 @@
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-module dstats.alloc;
@@ -148 +151 @@
-}
-
+// C functions, marked w/ nothrow.
+extern(C) nothrow int printf(in char *,...);
+extern(C) nothrow void exit(int);
+extern(C) nothrow void* malloc(size_t);
+extern(C) nothrow void* realloc(void*, size_t);
+extern(C) nothrow void* free(void*);
+alias malloc cstdmalloc;
+alias realloc cstdrealloc;
+alias free cfree;
+
-/**TempAlloc struct.  See TempAlloc project on Scrapple.*/
-struct TempAlloc {
@@ -154 +167 @@
-        size_t used;
-        block* prev;
+
+        void freeAll() {
+            if(prev !is null)
+                prev.freeAll();
+            if(space !is null)
+                cfree(space);
+            cfree(&this);
+        }
-    }
-
@@ -164 +185 @@
-         block* current;
-         block* freelist;
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-    enum blockSize = 4U * 1024U * 1024U;
+    enum nBookKeep = 1_048_576;
-    enum alignBytes = 16U;
-    static __thread State state;
-    static State mainThreadState;
-
+    static void die() nothrow {
+        printf("TempAlloc error: Out of memory.\0".ptr);
+        exit(1);
+    }
+
+    static void doubleSize(ref void*[] lastAlloc) nothrow {
+        size_t newSize = lastAlloc.length * 2;
+        void** ptr = cast(void**) crealloc(lastAlloc.ptr, newSize);
+        return ptr[0..newSize];
+    }
+
+    static void* cmalloc(size_t size) nothrow {
+        void* ret = cstdmalloc(size);
+        if(ret is null) {
+            try { GC.collect(); } catch {}
+            ret = cstdmalloc(size);
+
+            if(ret is null)
+                die();
+        }
+        return ret;
+    }
+
+    static void* crealloc(void* ptr, size_t size) nothrow {
+        void* ret = cstdrealloc(ptr, size);
+        if(ret is null) {
+            try { GC.collect(); } catch {}
+            ret = cstdrealloc(ptr, size);
+
+            if(ret is null)
+                die();
+        }
+        return ret;
+    }
+
-    static size_t getAligned(size_t nbytes) pure nothrow {
-        size_t rem = nbytes % alignBytes;
@@ -176 +246 @@
-    }
-
-
-
+
+
+
+
+
-
-        with(stateCopy) {
-
-
-
+
+
+
+
-            nblocks++;
-        }
-
-        state = stateCopy;
-hread_needLock
+nl()
-            mainThreadState = stateCopy;
-        return stateCopy;
@@ -196 +270 @@
-     * significant in some cases because it avoids a thread-local storage
-     * lookup.  Also used internally.*/
-
+nothrow 
-        // Believe it or not, even with builtin TLS, the thread_needLock()
-        // is worth it to avoid the TLS lookup.
-hread_needLock
+nl()
-                          state :
-                          mainThreadState;
@@ -209 +283 @@
-     * freed when frameFree() is called.  Returns a reference to the
-     * State class in case the caller wants to cache it for speed.*/
-
+nothrow 
-        return frameInit(getState);
-    }
@@ -215 +289 @@
-    /**Same as frameInit() but uses stateCopy cached on stack by caller
-     * to avoid a thread-local storage lookup.  Strictly a speed hack.*/
-
+nothrow 
-        with(stateCopy) {
-        if(totalAllocs == lastAlloc.length) // Should happen very infrequently.
-lastAlloc.length = lastAlloc.length * 2
+doubleSize(lastAlloc)
-        lastAlloc[totalAllocs] = cast(void*) frameIndex;
-        frameIndex = totalAllocs;
@@ -228 +302 @@
-    /**Frees all memory allocated by TempAlloc since the last call to
-     * frameInit().*/
-
+nothrow 
-        frameFree(getState);
-    }
@@ -234 +308 @@
-    /**Same as frameFree() but uses stateCopy cached on stack by caller
-    * to avoid a thread-local storage lookup.  Strictly a speed hack.*/
-
+nothrow 
-        with(stateCopy) {
-        while(totalAllocs > frameIndex + 1) {
@@ -244 +318 @@
-
-    /**Purely a convenience overload, forwards arguments to TempAlloc.malloc().*/
-
+nothrow 
-        return TempAlloc.malloc(args);
-    }
@@ -257 +331 @@
-     * Do not store the only reference to a GC-allocated object in
-     * TempAlloc-allocated memory.*/
-
+nothrow
-        return malloc(nbytes, getState);
-    }
@@ -263 +337 @@
-    /**Same as malloc() but uses stateCopy cached on stack by caller
-    * to avoid a thread-local storage lookup.  Strictly a speed hack.*/
-
+nothrow 
-        nbytes = getAligned(nbytes);
-        with(stateCopy) {
@@ -271 +345 @@
-                current.used += nbytes;
-            } else if(nbytes > blockSize) {
-GC.malloc(nbytes, GC.BlkAttr.NO_SCAN
+cmalloc(nbytes
-            } else if(nfree > 0) {
-                block* prev = freelist.prev;
@@ -282 +356 @@
-                ret = current.space;
-            } else { // Allocate more space.
-
-
+
+
+
-                nblocks++;
-                newBlock.prev = current;
@@ -291 +366 @@
-            }
-            if(totalAllocs == lastAlloc.length) // Should happen very infrequently.
-lastAlloc.length = lastAlloc.length * 2
+doubleSize(lastAlloc)
-            lastAlloc[totalAllocs++] = ret;
-            return ret;
@@ -301 +376 @@
-     * there's no need to pass a pointer in.  All bookkeeping for figuring
-     * out what to free is done internally.*/
-
+nothrow 
-        free(getState);
-    }
@@ -307 +382 @@
-    /**Same as free() but uses stateCopy cached on stack by caller
-    * to avoid a thread-local storage lookup.  Strictly a speed hack.*/
-
+nothrow 
-        with(stateCopy) {
-            void* lastPos = lastAlloc[--totalAllocs];
@@ -314 +389 @@
-            if(lastPos > current.space + blockSize ||
-               lastPos < current.space) {
-GC.
+c
-               return;
-            }
@@ -333 +408 @@
-                        block* last = freelist;
-                        freelist = freelist.prev;
-GC.
-GC.
+c
+c
-                        nfree--;
-                    }
@@ -354 +429 @@
- * in an array allocated by newStack because this memory is not
- * scanned by the GC.*/
-
+nothrow 
-    size_t bytes = size * T.sizeof;
-    T* ptr = cast(T*) TempAlloc.malloc(bytes);
@@ -362 +437 @@
-/**Same as newStack(size_t) but uses stateCopy cached on stack by caller
-* to avoid a thread-local storage lookup.  Strictly a speed hack.*/
-
+nothrow 
-    size_t bytes = size * T.sizeof;
-    T* ptr = cast(T*) TempAlloc.malloc(bytes, state);
@@ -369 +444 @@
-
-/**Creates a duplicate of an array on the TempAlloc struct.*/
-
+nothrow 
-    alias Mutable!(T) U;
-    U[] ret = newStack!(U)(data.length);
@@ -378 +453 @@
-/**Same as tempdup(T[]) but uses stateCopy cached on stack by caller
- * to avoid a thread-local storage lookup.  Strictly a speed hack.*/
-
+nothrow 
-    alias Mutable!(T) U;
-    U[] ret = newStack!(U)(data.length, state);

trunk/cor.d

@@ -3 +3 @@
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-module dstats.cor;

trunk/distrib.d

@@ -39 +39 @@
- *
- * normalCDF <=> normalDistribution
+ *
- * normalCDFR <=> normalDistributionCompl
+ *
- * invNormalCDF <=> normalDistributionComplInv
+ *
- * studentsTCDF <=> studentsTDistribution  (Note reversal in argument order)
+ *
- * invStudentsTCDF <=> studentsTDistributionInv (Again, arg order reversed)
+ *
- * binomialCDF <=> binomialDistribution
+ *
- * negBinomCDF <=> negativeBinomialDistribution
+ *
- * poissonCDF <=> poissonDistribution
+ *
- * chiSqrCDF <=> chiSqrDistribution
+ *
- * chiSqrCDFR <=> chiSqrDistributionCompl
+ *
- * invChiSqCDFR <=> chiSqrDistributionComplInv
+ *
- * fisherCDF <=> fDistribution
+ *
- * fisherCDFR <=> fDistributionCompl
+ *
- * invFisherCDFR <=> fDistributionComplInv
+ *
- * gammaCDF <=> gammaDistribution  (Note arg reversal)
+ *
- * gammaCDFR <=> gammaDistributionCompl  (Note arg reversal)
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-module dstats.distrib;
@@ -745 +763 @@
- * Normal probability density function (integrated from
- * minus infinity to x) is equal to p.
- *
- * For small arguments 0 < p < exp(-2), the program computes
- * z = sqrt( -2 log(p) );  then the approximation is
- * x = z - log(z)/z  - (1/z) P(1/z) / Q(1/z) .
- * For larger arguments,  x/sqrt(2 pi) = w + w^3 R(w^2)/S(w^2)) ,
- * where w = p - 0.5 .
- */
-real invNormalCDF(real p, real mean = 0, real sd = 1)

trunk/random.d

@@ -4 +4 @@
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-

trunk/sort.d

@@ -16 +16 @@
- * assert(foo == [1, 2, 3, 4, 5]);
- * assert(bar == [6, 7, 8, 5, 3]);
-
+
+
- * assert(bar == [8, 7, 6, 5, 3]);
- * assert(foo == [3, 2, 1, 4, 5]);
+ * assert(baz == [-1.0, 0, 1, -2, -3]);
- * ---
- *
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-module dstats.sort;
@@ -63 +68 @@
-}
-
-private 
+
-    if(input.length < 2) return;
-    T temp = input[0];
@@ -72 +77 @@
-}
-
-private 
+
-    if(input.length < 2) return;
-    T temp = input[$-1];
@@ -116 +121 @@
-}
-
-O(N^2) time 
+
- * case, O(log N) space, small constant term in time complexity.
- *
- O(N^2)
-worst case
+
+O(N<sup>2</sup>) worst case of naive quick sorts
- *
- * 1.  At each recursion, the median of the first, middle and last elements of
@@ -131 +136 @@
- *
- * 3.  After a much larger than expected amount of recursion has occured,
-
+
+
-T[0] qsort(alias compFun = lessThan, T...)(T data)
-in {
@@ -366 +372 @@
- * and U is a ulong* for calculating bubble sort distance, this can be called
- * as mergeSortTemp(D, D, D, T, T, T, U) or mergeSortTemp(D, D, D, T, T, T)
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-T[0] mergeSortTemp(alias compFun = lessThan, T...)(T data)
-in {
@@ -487 +509 @@
-}
-
-* log(N)^2
+log<sup>2</sup> N
- * time complexity, O(1) space complexity, stable.  Much slower than plain
- * old mergeSort(), so only use it if you really need the O(1) space.*/
@@ -686 +708 @@
-}
-
-^2) time worst, average case, O(1) space, VERY small
-
+<sup>2</sup>) time worst, average case, O(1) space, VERY
+small 
- * divide and conquer algorithms.  If last argument is a ulong*, increments
- * the dereference of this argument by the bubble sort distance between the
@@ -794 +816 @@
-}
-
-/**Given a set of data points entered through the addElement function,
- * maintains the invariant that the top N according to compFun will be
- * contained in the data structure.  Uses a heap internally, O(log N) insertion
- * time.  Good for finding the top N elements of a very large dataset that
- * cannot be sorted quickly in its entirety.  If less than N datapoints
- * have been entered, all are contained in the structure.
- *
- * Examples:
- * ---
-    Random gen;
-    gen.seed(unpredictableSeed);
-    uint[] nums = seq(0U, 100U);
-    auto less = TopN!(uint, "a < b")(10);
-    auto more = TopN!(uint, "a > b")(10);
-    randomShuffle(nums, gen);
-    foreach(n; nums) {
-        less.addElement(n);
-        more.addElement(n);
-    }
-    assert(less.getSorted == [0U, 1,2,3,4,5,6,7,8,9]);
-    assert(more.getSorted == [99U, 98, 97, 96, 95, 94, 93, 92, 91, 90]);
-    ---*/
-struct TopN(T, alias compFun = greaterThan) {
-private:
-    alias binaryFun!(compFun) comp;
-    uint n;
-    uint nAdded;
-
-    T[] nodes;
-public:
-    /**The variable ntop controls how many elements are retained.*/
-    this(uint ntop) {
-        n = ntop;
-        nodes = new T[n];
-    }
-
-    /**Insert an element into the topN struct.*/
-    void addElement(T elem) {
-        if(nAdded < n) {
-            nodes[nAdded] = elem;
-            if(nAdded == n - 1) {
-                makeMultiHeap!(comp)(nodes);
-            }
-            nAdded++;
-        } else if(nAdded >= n) {
-             if(comp(elem, nodes[0])) {
-                nodes[0] = elem;
-                multiSiftDown!(comp)(nodes, 0, nodes.length);
-            }
-        }
-    }
-
-    /**Get the elements currently in the struct.  Returns a reference to
-     * internal state, elements will be in an arbitrary order.  Cheap.*/
-    const(T)[] getElements() const {
-        return nodes[0..min(n, nAdded)];
-    }
-
-    /**Returns the elements sorted by compFun.  The array returned is a
-     * duplicate of the input array.  Not cheap.*/
-    T[] getSorted() const {
-        return qsort!(comp)(nodes[0..min(n, nAdded)].dup);
-    }
-}
-
-unittest {
-    alias TopN!(uint, "a < b") TopNLess;
-    alias TopN!(uint, "a > b") TopNGreater;
-    Random gen;
-    gen.seed(unpredictableSeed);
-    uint[] nums = new uint[100];
-    foreach(i, ref n; nums) {
-        n = i;
-    }
-    foreach(i; 0..100) {
-        auto less = TopNLess(10);
-        auto more = TopNGreater(10);
-        randomShuffle(nums, gen);
-        foreach(n; nums) {
-            less.addElement(n);
-            more.addElement(n);
-        }
-        assert(less.getSorted == [0U, 1,2,3,4,5,6,7,8,9]);
-        assert(more.getSorted == [99U, 98, 97, 96, 95, 94, 93, 92, 91, 90]);
-    }
-    foreach(i; 0..100) {
-        auto less = TopNLess(10);
-        auto more = TopNGreater(10);
-        randomShuffle(nums, gen);
-        foreach(n; nums[0..5]) {
-            less.addElement(n);
-            more.addElement(n);
-        }
-        assert(less.getSorted == qsort!("a < b")(nums[0..5]));
-        assert(more.getSorted == qsort!("a > b")(nums[0..5]));
-    }
-    writeln("Passed TopN test.");
-}
-
-/**Returns the kth largest/smallest element (depending on compFun, 0-indexed)
- * in the input array in O(N) time.  Allocates memory, does not modify input
@@ -920 +843 @@
- * ---
- * auto foo = [3, 1, 5, 4, 2].dup;
-Elem
-Elem
+Smallest
+Smallest
- * foreach(elem; foo[0..1]) {
- *     assert(elem <= foo[1]);
- * }
- * foreach(elem; foo[2..$]) {
-
+[1]
- * }
-
-
+
+
+
+
-ArrayElemType!(T[0]) partitionK(alias compFun = lessThan, T...)(T data, int k)
-in {
@@ -1022 +947 @@
-}
-
+/**Given a set of data points entered through the addElement function,
+ * maintains the invariant that the top N according to compFun will be
+ * contained in the data structure.  Uses a heap internally, O(log N) insertion
+ * time.  Good for finding the largest/smallest N elements of a very large
+ * dataset that cannot be sorted quickly in its entirety, and may not even fit
+ * in memory. If less than N datapoints have been entered, all are contained in
+ * the structure.
+ *
+ * Examples:
+ * ---
+ * Random gen;
+ * gen.seed(unpredictableSeed);
+ * uint[] nums = seq(0U, 100U);
+ * auto less = TopN!(uint, "a < b")(10);
+ * auto more = TopN!(uint, "a > b")(10);
+ * randomShuffle(nums, gen);
+ * foreach(n; nums) {
+ *     less.addElement(n);
+ *     more.addElement(n);
+ * }
+ *  assert(less.getSorted == [0U, 1,2,3,4,5,6,7,8,9]);
+ *  assert(more.getSorted == [99U, 98, 97, 96, 95, 94, 93, 92, 91, 90]);
+ *  ---
+ */
+struct TopN(T, alias compFun = greaterThan) {
+private:
+    alias binaryFun!(compFun) comp;
+    uint n;
+    uint nAdded;
+
+    T[] nodes;
+public:
+    /** The variable ntop controls how many elements are retained.*/
+    this(uint ntop) {
+        n = ntop;
+        nodes = new T[n];
+    }
+
+    /** Insert an element into the topN struct.*/
+    void addElement(T elem) {
+        if(nAdded < n) {
+            nodes[nAdded] = elem;
+            if(nAdded == n - 1) {
+                makeMultiHeap!(comp)(nodes);
+            }
+            nAdded++;
+        } else if(nAdded >= n) {
+             if(comp(elem, nodes[0])) {
+                nodes[0] = elem;
+                multiSiftDown!(comp)(nodes, 0, nodes.length);
+            }
+        }
+    }
+
+    /**Get the elements currently in the struct.  Returns a reference to
+     * internal state, elements will be in an arbitrary order.  Cheap.*/
+    const(T)[] getElements() const {
+        return nodes[0..min(n, nAdded)];
+    }
+
+    /**Returns the elements sorted by compFun.  The array returned is a
+     * duplicate of the input array.  Not cheap.*/
+    T[] getSorted() const {
+        return qsort!(comp)(nodes[0..min(n, nAdded)].dup);
+    }
+}
+
+unittest {
+    alias TopN!(uint, "a < b") TopNLess;
+    alias TopN!(uint, "a > b") TopNGreater;
+    Random gen;
+    gen.seed(unpredictableSeed);
+    uint[] nums = new uint[100];
+    foreach(i, ref n; nums) {
+        n = i;
+    }
+    foreach(i; 0..100) {
+        auto less = TopNLess(10);
+        auto more = TopNGreater(10);
+        randomShuffle(nums, gen);
+        foreach(n; nums) {
+            less.addElement(n);
+            more.addElement(n);
+        }
+        assert(less.getSorted == [0U, 1,2,3,4,5,6,7,8,9]);
+        assert(more.getSorted == [99U, 98, 97, 96, 95, 94, 93, 92, 91, 90]);
+    }
+    foreach(i; 0..100) {
+        auto less = TopNLess(10);
+        auto more = TopNGreater(10);
+        randomShuffle(nums, gen);
+        foreach(n; nums[0..5]) {
+            less.addElement(n);
+            more.addElement(n);
+        }
+        assert(less.getSorted == qsort!("a < b")(nums[0..5]));
+        assert(more.getSorted == qsort!("a > b")(nums[0..5]));
+    }
+    writeln("Passed TopN test.");
+}
+
-// Verify that there are no TempAlloc memory leaks anywhere in the code covered
-// by the unittest.  This should always be the last unittest of the module.
@@ -1029 +1055 @@
-    assert(TAState.nblocks < 2);
-}
+

trunk/stats.d

@@ -3 +3 @@
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-module dstats.stats;

trunk/summary.d

@@ -7 +7 @@
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
@@ -169 +172 @@
-    }
-
+    ///
-    string toString() {
-        return to!(string)(mean);
@@ -268 +272 @@
-    }
-
+    ///
-    string toString() {
-        return format("N = ", cast(ulong) _k, "\nMean = ", mean, "\nVariance = ",
@@ -422 +427 @@
-    }
-
+    ///
-    string toString() {
-        return format("N = ", cast(ulong) _k, "\nMean = ", mean, "\nVariance = ",
@@ -496 +502 @@
-    real max;
-
+    ///
-    string toString() {
-        return format("N = ", N, "\nMean = ", mean, "\nVariance = ",
@@ -504 +511 @@
-
-/**Calculates all summary dstats (mean, variance, standard dev., skewness
-
+)
-Summary summary(T)(const T[] data) {
-    OnlineSummary summ;

trunk/tests.d

@@ -3 +3 @@
- * Author:  David Simcha
- *
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-module dstats.tests;
-