Official DMD compiler written in D

[Era Scarecrow]

  Eep, seems I hit send...

On Thursday, 10 January 2013 at 05:47:01 UTC, H. S. Teoh wrote:
> The basic idea behind static AA literals is to use CTFE to 
> compute the hashes of the keys, and therefore which slot(s) 
> they will fall in, at compile time. Armed with this 
> information, we can create an array of slots at compile-time 
> that contains the AA entries by declaring each slot as a static 
> variable and using the slot assignment information to 
> initialize the hash table (array of pointers to slots) to point 
> to these slots.

  Hmmm somehow that doesn't seem like a good idea; I mean it will 
work....

  Alternative is to sorta have a pair of static arrays, then 
either use a balanced tree, or a modulus to best hold (and 
separate) the values.

  Modulus based: It could be like...

   //T obviously replace with appropriate type
   ref T AA_lookup(name publicName)(uint hash) {
     //offset for part1
     //could be external to..
     immutable static int offsets[];  //no need for pointers, 
right?
     immutable static T values[]; //contains actual item data

     enum mod; //divider for table.
     uint result = hash % mod;

     //or branch to return empty? But can't be ref then...
     assert(offsets[result] != -1);

     return values[offsets[result]];
   }

  Then your CTFE increases the mod in it's calculations until 
every element can fit only once, and make the offsets based on 
them. Default values would be -1 (range error if called), course 
if it's mod is rather large and wastes a lot of space then 
perhaps it falls back on the tree structure (in those cases, > 3x 
of array size)


  Tree: I don't mind a minor performance hit, log(n) is a very 
small hit in my mind. In that case a statically created tree is 
rather easy. AA's created ahead of time are likely rather small 
(<1 Million elements). So a tree structure of:

  struct Node(T) {
    //pointers don't seem like they are needed;
    //Can even be ushorts or ubytes if small enough.
    uint left, right;
    T* value;
  }

  You get the idea.