Robert Fraser wrote:
nobody wrote:
$ g++ alloc.cpp -o alloc
$ time ./alloc
real 0m1.946s
user 0m1.688s
sys 0m0.256s
$ dmd -O -release allocd.d
$ time ./allocd
real 0m22.734s
user 0m22.353s
sys 0m0.360s
$ cat alloc.cpp
#include <vector>
typedef std::vector<int> intvec;
typedef intvec* intvecp;
int main() {
int i, n = 20000000;
intvecp* iva;
iva = new intvecp[n];
for (i = n; i-- > 0; ) {
iva[i] = new intvec();
}
return 0;
}
$ cat allocd.d
int main() {
int i, n = 20000000;
Object[] oa;
oa = new Object[n];
for (i = n; i-- > 0; ) {
oa[i] = new Object();
}
return 0;
}
I use this a structure for arena-based memory allocation (attached).
Example of use:
import candy.util.MemPool
MemStack!() stack;
class MyObject
{
mixin MemPoolNew!(stack);
}
int main()
{
stack.push();
int i, n = 20000000;
MyObject[] oa;
oa = new MyObject[n];
for (i = n; i-- > 0; )
{
oa[i] = new MyObject();
}
stack.pop();
return 0;
}
The push() and pop() allows memory to be allocated and deallocated as
large blocks. However, you shouldn't need to deallocate manually -- it's
GCed memory, so ideally the GC should free it when it's no longer
referenced. That being said, I've run some tests, and the GC will free
it *eventually*, but it allocates 4-6x as much memory as it needs before
it starts freeing it, even when GC.collect() is called manually.
--------------------
/**
* Provides a pool of GCed memory to allocate things from a block.
* This maintains cache coherency for related types (i.e. tree nodes).
* It doesn't garuntee any ordering, though, the array struct should be
* used for that. Also, everything has to be freed at once, freeing one
* portion of this has no effect.
*
* Based on a similar concept posted by bearophile at:
*
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=88227
*/
public struct MemPool(size_t BLOCK_SIZE = 1 << 14)
{
private void* next; // Next available block
private void* end; // End of the current block
private void*[] blocks;
public void* alloc(size_t sz)
{
sz = ((sz + 7) & ~7); // Next multiple of 8 if this isn't a
multiple of 8
if (this.next + sz >= this.end)
{
void* blk = GC.calloc(BLOCK_SIZE);
this.blocks.length = this.blocks.length + 1;
this.blocks[$ - 1] = blk;
this.next = blk;
this.end = blk + BLOCK_SIZE;
}
void* ret = this.next;
this.next += sz;
return ret;
}
public void free()
{
foreach(blk; this.blocks)
GC.free(blk);
this.blocks = null;
this.blocks.length = 0;
this.next = null;
this.end = null;
}
}
/**
* Wrapper for MemPool that allocates the given struct
*/
public struct StructPool(T)
{
private MemPool!() pool;
public T* alloc() { return cast(T*) pool.alloc(T.sizeof); }
}
public struct MemStack(size_t BLOCK_SIZE = 1 << 14)
{
private Stack!(MemPool!(BLOCK_SIZE)*, 16, true, true) stack;
public static const size_t MAX_ALLOC = BLOCK_SIZE;
public void* alloc(size_t sz) { return
stack.peek().alloc(sz); }
public void push() { stack.push(new
MemPool!(BLOCK_SIZE)); }
public void pop() {
stack.pop().free(); }
}
/**
* Placement new mixin for allocating from a memory pool. Benchmarks
show this
* as faster than the D new in real usage (i.e. the parser runs about 1.2x
* faster using this).
*/
public template MemPoolNew(alias Pool)
{
version(NoMemPool) { } else
{
public final new(uint sz) { return Pool.alloc(sz); }
public final delete(void *p) { }
}
}
Oops, that needs another module. Okay, both are attached in a
compile-able form.
/*******************************************************************************
* Copyright (c) 2008-2009 Robert Fraser
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*******************************************************************************/
module candy.util.memory;
import tango.core.Memory : GC;
import candy.util.array;
/**
* Provides a pool of GCed memory to allocate things from a block.
* This maintains cache coherency for related types (i.e. tree nodes).
* It doesn't garuntee any ordering, though, the array struct should be
* used for that. Also, everything has to be freed at once, freeing one
* portion of this has no effect.
*
* Based on a similar concept posted by bearophile at:
*
http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=88227
*/
public struct MemPool(size_t BLOCK_SIZE = 1 << 14)
{
private void* next; // Next available block
private void* end; // End of the current block
private void*[] blocks;
public void* alloc(size_t sz)
{
sz = ((sz + 7) & ~7); // Next multiple of 8 if this isn't a multiple of
8
if (this.next + sz >= this.end)
{
void* blk = GC.calloc(BLOCK_SIZE);
this.blocks.length = this.blocks.length + 1;
this.blocks[$ - 1] = blk;
this.next = blk;
this.end = blk + BLOCK_SIZE;
}
void* ret = this.next;
this.next += sz;
return ret;
}
public void free()
{
foreach(blk; this.blocks)
GC.free(blk);
this.blocks = null;
this.blocks.length = 0;
this.next = null;
this.end = null;
}
}
/**
* Wrapper for MemPool that allocates the given struct
*/
public struct StructPool(T)
{
private MemPool!() pool;
public T* alloc() { return cast(T*) pool.alloc(T.sizeof); }
}
public struct MemStack(size_t BLOCK_SIZE = 1 << 14)
{
private Stack!(MemPool!(BLOCK_SIZE)*, 16, true, true) stack;
public static const size_t MAX_ALLOC = BLOCK_SIZE;
public void* alloc(size_t sz) { return stack.peek().alloc(sz);
}
public void push() { stack.push(new MemPool!(BLOCK_SIZE));
}
public void pop() { stack.pop().free();
}
}
/**
* Placement new mixin for allocating from a memory pool. Benchmarks show this
* as faster than the D new in real usage (i.e. the parser runs about 1.2x
* faster using this).
*/
public template MemPoolNew(alias Pool)
{
version(NoMemPool) { } else
{
public final new(uint sz) { return Pool.alloc(sz); }
public final delete(void *p) { }
}
}
/*******************************************************************************
* Copyright (c) 2008-2009 Robert Fraser
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* http://www.eclipse.org/legal/epl-v10.html
*******************************************************************************/
module candy.util.array;
import tango.core.BitManip : bsr;
import tango.core.Traits : isReferenceType;
import tango.core.Memory : GC;
import tango.stdc.string : memcpy, memset;
public struct Array(T, size_t START_SIZE = 16, bool doScan =
isReferenceType!(T),
alias Realloc = GC.realloc, alias Free = GC.free)
{
T* arr = null;
size_t len = 0;
size_t cap = 0;
public void opCatAssign(T v)
{
len++;
if(len >= cap)
grow(cap ? cap * 2 : START_SIZE);
arr[len - 1] = v;
}
public void opCatAssign(T[] v)
{
int newlen = len + v.length;
if(newlen > cap)
{
if(newlen < START_SIZE)
grow(START_SIZE);
else
grow(2 << bsr(newlen + 1)); // Next power of 2
}
memcpy(arr + len, v.ptr, (newlen - len) * T.sizeof);
len = newlen;
}
public void opCatAssign(Array!(T) v)
{
opCatAssign(v.toArray());
}
public T[] toArray()
{
return arr[0 .. len];
}
public size_t length()
{
return len;
}
public T opIndex(size_t n)
{
assert(n < len);
return arr[n];
}
public void opIndexAssign(T v, size_t n)
{
assert(n < len);
arr[n] = v;
}
public T[] opSlice()
{
return toArray();
}
public T[] opSlice(size_t low, size_t high)
{
assert(low <= high);
assert(high < len);
return arr[low .. high];
}
public void opSliceAssign(T v)
{
arr[0 .. len] = v;
}
public void opSliceAssign(T v, size_t low, size_t high)
{
assert(low <= high);
assert(high < len);
arr[low .. high] = v;
}
public void opSliceAssign(T[] v, size_t low, size_t high)
{
assert(low <= high);
assert(high < len);
assert(v.length == high - low);
memcpy(arr + low, v.ptr, v.length * T.sizeof);
}
public void opSliceAssign(Array!(T) v, size_t low, size_t high)
{
opSliceAssign(v.toArray(), low, high);
}
public bool isEmpty()
{
return len == 0;
}
public void clear()
{
len = 0;
}
public void free()
{
if(arr)
{
Free(arr);
arr = null;
}
len = 0;
}
public void zero()
{
if(arr)
{
memset(arr, 0, cap * T.sizeof);
Free(arr);
arr = null;
}
len = 0;
}
public void addNull()
{
len++;
if(len >= cap)
grow(cap ? cap * 2 : START_SIZE);
}
public bool contains(T elem)
{
for(int i = 0; i < len; i++)
if(arr[i] == elem)
return true;
return false;
}
static if(doScan)
private static const BlkAttr = 0;
else
private static const BlkAttr = GC.BlkAttr.NO_SCAN;
private void grow(size_t sz)
{
arr = cast(T*) Realloc(arr, sz * T.sizeof, BlkAttr);
static if(doScan)
{
memset(arr + cap, 0, (sz - cap) * T.sizeof);
}
cap = sz;
}
}
public struct Stack(T, size_t START_SIZE = 16, bool doScan = true, bool
zeroOnPop = false,
alias ArrayType = Array, ArrayArgs...)
{
private ArrayType!(T, START_SIZE, doScan, ArrayArgs) arr;
public void pushNull()
{
arr.addNull();
}
public void push(T v)
{
arr ~= v;
}
public T pop()
{
assert(arr.len > 0);
T ret = arr.arr[arr.len - 1];
static if(zeroOnPop)
arr.arr[arr.len - 1] = T.init;
arr.len--;
return ret;
}
public T peek()
{
assert(arr.len > 0);
return arr.arr[arr.len - 1];
}
public bool isEmpty()
{
return arr.isEmpty();
}
public void clear()
{
static if(zeroOnPop)
arr.zero();
else
arr.clear();
}
public bool contains(T elem)
{
return arr.contains(elem);
}
public T[] toArray()
{
return arr.toArray();
}
}
