changeset 1633:5c0cebff9be8

Improve array append performance. Actually use the appropriate runtime function, instead of just growing the array by one!
author Christian Kamm <kamm incasoftware de>
date Sun, 14 Feb 2010 10:11:05 +0100
parents 8c37dcd7cfde
children 9cc791423e20
files gen/arrays.cpp gen/arrays.h gen/runtime.cpp gen/toir.cpp tango-0.99.9.patch
diffstat 5 files changed, 95 insertions(+), 31 deletions(-) [+]
line wrap: on
line diff
--- a/gen/arrays.cpp	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/arrays.cpp	Sun Feb 14 10:11:05 2010 +0100
@@ -474,7 +474,7 @@
 
     // build dims
     LLValue* dimsArg = DtoArrayAlloca(Type::tsize_t, ndims, ".newdims");
-    LLValue* firstDim = NULL; 
+    LLValue* firstDim = NULL;
     for (size_t i=0; i<ndims; ++i)
     {
         LLValue* dim = dims[i]->getRVal();
@@ -532,30 +532,29 @@
 }
 
 //////////////////////////////////////////////////////////////////////////////////////////
-DSliceValue* DtoCatAssignElement(DValue* array, Expression* exp)
+void DtoCatAssignElement(Type* arrayType, DValue* array, Expression* exp)
 {
     Logger::println("DtoCatAssignElement");
     LOG_SCOPE;
 
     assert(array);
 
-    LLValue* idx = DtoArrayLen(array);
-    LLValue* one = DtoConstSize_t(1);
-    LLValue* len = gIR->ir->CreateAdd(idx,one,"tmp");
+    DValue *expVal = exp->toElem(gIR);
+    LLValue *valueToAppend;
+    if (expVal->isLVal())
+        valueToAppend = expVal->getLVal();
+    else {
+        valueToAppend = DtoAlloca(expVal->getType(), ".appendingElementOnStack");
+        DtoStore(expVal->getRVal(), valueToAppend);
+    }
 
-    DValue* newdim = new DImValue(Type::tsize_t, len);
-    DSliceValue* slice = DtoResizeDynArray(array->getType(), array, newdim);
+    LLFunction* fn = LLVM_D_GetRuntimeFunction(gIR->module, "_d_arrayappendcT");
+    LLSmallVector<LLValue*,3> args;
+    args.push_back(DtoTypeInfoOf(arrayType));
+    args.push_back(DtoBitCast(array->getLVal(), getVoidPtrType()));
+    args.push_back(DtoBitCast(valueToAppend, getVoidPtrType()));
 
-    LLValue* ptr = slice->ptr;
-    ptr = llvm::GetElementPtrInst::Create(ptr, idx, "tmp", gIR->scopebb());
-
-    DValue* dptr = new DVarValue(exp->type, ptr);
-
-    DValue* e = exp->toElem(gIR);
-
-    DtoAssign(exp->loc, dptr, e);
-
-    return slice;
+    gIR->CreateCallOrInvoke(fn, args.begin(), args.end(), ".appendedArray");
 }
 
 //////////////////////////////////////////////////////////////////////////////////////////
@@ -980,7 +979,7 @@
     else if (totype->ty == Tsarray) {
         if (Logger::enabled())
             Logger::cout() << "to sarray" << '\n';
-        
+
         size_t tosize = ((TypeSArray*)totype)->dim->toInteger();
 
         if (fromtype->ty == Tsarray) {
@@ -1004,9 +1003,9 @@
             size_t i = (tosize * totype->nextOf()->size() - 1) / fromtype->nextOf()->size();
             DConstValue index(Type::tsize_t, DtoConstSize_t(i));
             DtoArrayBoundsCheck(loc, u, &index, false);
-            
+
             rval = DtoArrayPtr(u);
-            rval = DtoBitCast(rval, getPtrToType(tolltype));            
+            rval = DtoBitCast(rval, getPtrToType(tolltype));
         }
     }
     else if (totype->ty == Tbool) {
--- a/gen/arrays.h	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/arrays.h	Sun Feb 14 10:11:05 2010 +0100
@@ -24,7 +24,7 @@
 DSliceValue* DtoNewMulDimDynArray(Loc& loc, Type* arrayType, DValue** dims, size_t ndims, bool defaultInit=true);
 DSliceValue* DtoResizeDynArray(Type* arrayType, DValue* array, DValue* newdim);
 
-DSliceValue* DtoCatAssignElement(DValue* arr, Expression* exp);
+void DtoCatAssignElement(Type* type, DValue* arr, Expression* exp);
 DSliceValue* DtoCatAssignArray(DValue* arr, Expression* exp);
 DSliceValue* DtoCatArrays(Type* type, Expression* e1, Expression* e2);
 DSliceValue* DtoCatArrayElement(Type* type, Expression* exp1, Expression* exp2);
--- a/gen/runtime.cpp	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/runtime.cpp	Sun Feb 14 10:11:05 2010 +0100
@@ -326,6 +326,17 @@
         llvm::Function::Create(fty, llvm::GlobalValue::ExternalLinkage, fname2, M);
     }
 
+    // void* _d_arrayappendcT(TypeInfo ti, void* array, void* element)
+    {
+        llvm::StringRef fname("_d_arrayappendcT");
+        std::vector<const LLType*> types;
+        types.push_back(typeInfoTy);
+        types.push_back(voidPtrTy);
+        types.push_back(voidPtrTy);
+        const llvm::FunctionType* fty = llvm::FunctionType::get(rt_array(byteTy), types, false);
+        llvm::Function::Create(fty, llvm::GlobalValue::ExternalLinkage, fname, M);
+    }
+
     // Object _d_allocclass(ClassInfo ci)
     {
         llvm::StringRef fname("_d_allocclass");
--- a/gen/toir.cpp	Sun Sep 13 22:15:33 2009 +0300
+++ b/gen/toir.cpp	Sun Feb 14 10:11:05 2010 +0100
@@ -624,7 +624,7 @@
     // valid array ops would have been transformed by optimize
     if ((t1->ty == Tarray || t1->ty == Tsarray) &&
         (t2->ty == Tarray || t2->ty == Tsarray)
-       ) 
+       )
     {
         base->error("Array operation %s not recognized", base->toChars());
         fatal();
@@ -1013,7 +1013,7 @@
         return DtoBitCast(gep, DtoType(type));
     }
     else if (
-        e1->op == TOKstructliteral || 
+        e1->op == TOKstructliteral ||
         e1->op == TOKslice)
     {
         error("non-constant expression '%s'", toChars());
@@ -1138,7 +1138,7 @@
         // decide whether this function needs to be looked up in the vtable
         //
         bool vtbllookup = fdecl->isAbstract() || (!fdecl->isFinal() && fdecl->isVirtual());
-        
+
         // even virtual functions are looked up directly if super or DotTypeExp
         // are used, thus we need to walk through the this expression and check
         Expression* e = e1;
@@ -1150,7 +1150,7 @@
             else
                 break;
         }
-        
+
         //
         // look up function
         //
@@ -1237,12 +1237,12 @@
         arrptr = DtoGEP1(l->getRVal(),r->getRVal());
     }
     else if (e1type->ty == Tsarray) {
-        if(global.params.useArrayBounds) 
+        if(global.params.useArrayBounds)
             DtoArrayBoundsCheck(loc, l, r, false);
         arrptr = DtoGEP(l->getRVal(), zero, r->getRVal());
     }
     else if (e1type->ty == Tarray) {
-        if(global.params.useArrayBounds) 
+        if(global.params.useArrayBounds)
             DtoArrayBoundsCheck(loc, l, r, false);
         arrptr = DtoArrayPtr(l);
         arrptr = DtoGEP1(arrptr,r->getRVal());
@@ -1769,7 +1769,7 @@
 
     // class invariants
     if(
-        global.params.useInvariants && 
+        global.params.useInvariants &&
         condty->ty == Tclass &&
         !((TypeClass*)condty)->sym->isInterfaceDeclaration())
     {
@@ -1780,7 +1780,7 @@
     }
     // struct invariants
     else if(
-        global.params.useInvariants && 
+        global.params.useInvariants &&
         condty->ty == Tpointer && condty->nextOf()->ty == Tstruct &&
         (invdecl = ((TypeStruct*)condty->nextOf())->sym->inv) != NULL)
     {
@@ -2234,8 +2234,7 @@
     Type* e2type = e2->type->toBasetype();
 
     if (e2type == elemtype) {
-        DSliceValue* slice = DtoCatAssignElement(l,e2);
-        DtoAssign(loc, l, slice);
+        DtoCatAssignElement(e1type, l, e2);
     }
     else if (e1type == e2type) {
         DSliceValue* slice = DtoCatAssignArray(l,e2);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tango-0.99.9.patch	Sun Feb 14 10:11:05 2010 +0100
@@ -0,0 +1,55 @@
+Index: tango/core/rt/compiler/ldc/rt/lifetime.d
+===================================================================
+--- tango/core/rt/compiler/ldc/rt/lifetime.d	(revision 5368)
++++ tango/core/rt/compiler/ldc/rt/lifetime.d	(working copy)
+@@ -786,6 +786,7 @@
+     return *cast(long*)px;
+ }
+ 
+++/
+ 
+ /**
+  *
+@@ -849,10 +850,11 @@
+ 
+ 
+ /**
+- *
++ * Appends a single element to an array.
+  */
+-extern (C) byte[] _d_arrayappendcT(TypeInfo ti, ref byte[] x, ...)
++extern (C) byte[] _d_arrayappendcT(TypeInfo ti, void* array, void* element)
+ {
++    auto x = cast(byte[]*)array;
+     auto sizeelem = ti.next.tsize();            // array element size
+     auto info = gc_query(x.ptr);
+     auto length = x.length;
+@@ -879,16 +881,16 @@
+         assert(newcap >= newlength * sizeelem);
+         newdata = cast(byte *)gc_malloc(newcap + 1, info.attr);
+         memcpy(newdata, x.ptr, length * sizeelem);
+-        (cast(void**)(&x))[1] = newdata;
++        (cast(void**)x)[1] = newdata;
+     }
+   L1:
+-    byte *argp = cast(byte *)(&ti + 2);
++    byte *argp = cast(byte *)element;
+ 
+-    *cast(size_t *)&x = newlength;
++    *cast(size_t *)x = newlength;
+     x.ptr[length * sizeelem .. newsize] = argp[0 .. sizeelem];
+     assert((cast(size_t)x.ptr & 15) == 0);
+     assert(gc_sizeOf(x.ptr) > x.length * sizeelem);
+-    return x;
++    return *x;
+ }
+ 
+ 
+@@ -1128,6 +1130,7 @@
+     return result;
+ }
+ 
++/+
+ 
+ /**
+  *