small maps

[Alex Tatumizer]

From changelog, I see heroic efforts directed to optimization of maps.
There's one very common use case not specifically optimized for: small maps with string keys (most JSON objects belongs to this category).
I did some experiments back in the era of Pigeon Map, which showed that up to a certain limit (which may be as big as 12 keys, or even 16 - it depends), plain array of key/value pairs is faster. You don't need to compute hashCode at all, just compare strings, and you can use some heuristics (like tentatively comparing only first char) to avoid calling into runtime.
Just wondering whether this idea was explored and rejected, or just overlooked.
(Sorry for unsolicited advice)

[Andreas Kirsch]

AngularDart does that a lot internally.

--
For other discussions, see https://groups.google.com/a/dartlang.org/
 
For HOWTO questions, visit http://stackoverflow.com/tags/dart
 
To file a bug report or feature request, go to http://www.dartbug.com/new

To unsubscribe from this group and stop receiving emails from it, send an email to misc+uns...@dartlang.org.

[Vyacheslav Egorov]

+koda

I suspect you are asking about compact map representation that landed recently?

We definitely discussed it, because new representation allocates hash and key/value storage separately, so you could use linear search up to a certain map size. 

But I don't know if we checked the performance for such variant. 

// Vyacheslav Egorov

[Lasse R.H. Nielsen]

Linear lookup can be better, but the cut-off point isn't always as big as 12-16 keys. If you compare a VM const-map with a plain HashMap, it happens around six entries (all one-character keys). Ofcourse that could also be due to other inefficiencies than the linear lookup.

I fear that adding an unpredictable conditional branch as the first part of lookup will also be costly (and the extra code might prevent inlining), but again, only tests on realistic programs can tell how much it costs.

I think there are other things we can do for JSON parsing that will have bigger impact. Often large JSON files have many maps with the same structure. Reusing the structure (and the key strings with it) could potentially give a big memory win.

/L

--

Lasse R.H. Nielsen - l...@google.com  

'Faith without judgement merely degrades the spirit divine'
Google Denmark ApS - Frederiksborggade 20B, 1 sal - 1360 København K - Denmark - CVR nr. 28 86 69 84

[Daniel Andersson]

As a data point, Dart2JS has its own special-casing of small maps and sets (Maplet/Setlet). As part of the map overhaul, I will look into whether it makes sense to bring this also to the standard Map/Set implementation.

[Alex Tatumizer]

Don't know how helpful the following exploration can be, but anyway...

Tried different idea: we use hashCodes, but store them in separate array. So altogether we have 3 arrays (hashCodes, keys, values). No restrictions on keys. If any hashcode collision is detected, or max size is reached, it falls back on normal map.

Turns out, linear search (if done correctly!) beats current map implementation hands down. The cutoff is around 25 elements.

Here are the results (tested on version 1.9.0.dev_08_04 (DEV)
David vs Goliath:
6 items:  5% slower
8 items:  20% faster!
10 items: 17% faster!
12 items: 14% faster!
16 items: 7% faster!
24 items: 1% faster!

Here's the full text of the etude (I didn't implement all Map methods, but the rest is obvious). For readability, no private members.

class SmallMap {
  static const int MAX=32; // to be chosen carefully. Maybe 16 is optimal.
  var keys=new List(MAX);
  var hashCodes=new List<int>(MAX);
  var values=new List(MAX);
  var fallbackMap;
  int currentSize=0;
  int _findIndex(hashCode) {
     for (int i=0, j=currentSize-1; j>=i; i++, j--) {
        if (hashCodes[i]==hashCode) return i;
        if (hashCodes[j]==hashCode) return j;
     }
     return -1;
  }
  _createFallback() {
    print ("creating fallback!");
    fallbackMap=new Map();
    for (int i=0; i<currentSize; i++) {
      fallbackMap[keys[i]]=values[i];
    }
  }
  operator [](key) {
     if (fallbackMap!=null) {
       return fallbackMap[key];
     }
     int index=_findIndex(key.hashCode);
     return index>=0 && keys[index]==key ? values[index] : null;
  }
  operator []=(key,value) {
    if (fallbackMap!=null) {
      fallbackMap[key]=value;
      return;
    }
    int hashCode=key.hashCode;    
    int index=_findIndex(hashCode);
    if (index>=0) {
        if (keys[index]==key) {      
           values[index]=value;
        } else {
           _createFallback();
           fallbackMap[key]=value;
        }
    } else if (currentSize==MAX) {
      _createFallback();
      fallbackMap[key]=value;
    } else {  
       keys[currentSize]=key;
       values[currentSize]=value;
       hashCodes[currentSize]=hashCode;
       currentSize++;
    }  
  }

}

[Alex Tatumizer]

After small improvements (changing MAX to 16, using Int32List for hashCodes instead of generic List), the lead against standard Map grows to 30-40%.

Unfortunately, even after that, it's by 70%+ slower than standard HashMap in java :(

Maybe I'm missing some other possibilities in SmallMap?

(BTW, turns out that the trick with search in both directions is not that effective on small arrays.).

[Vyacheslav Egorov]

Nice experiments Alex!

Yes, this matches my expectations --- having linear search for small sizes is definitely better than hash lookup.  

Out of curiousity: could you put your benchmarks somewhere (both Dart and Java)? Thanks.

// Vyacheslav Egorov

--

[Alex Tatumizer]

I will reduce the tests to the bare bones tomorrow (right now, I have a kind of "framework" for testing, hehe).

Yeah, it would be nice if you could take a look at the generated code (even for a fragment I posted above) to see what's wrong with it. How java can be more efficient than that? If memory doesn't fail me, java uses DIV by prime in HashMap while looking for a bucket, and this DIV alone "weighs" more than my entire program. Strange.

(I will double-check though before posting, maybe I made some miscalculation somewhere)

[Alex Tatumizer]

After further improvements, got within 25% of java (still not clear what makes dart version slower)

dart benchmark and revised source of SmallMap

https://gist.github.com/tatumizer/91a887e802594becaa8c

java benchmark

https://gist.github.com/tatumizer/054124df0b73dec4f9f5

[Alex Tatumizer]

Yeah, string equality is very slow

To check, tested against homegrown method IN PURE DART

bool isEqualString(s1, s2) {

  // no need to check type of s1, it's supposed to be String function anyway

  if (s2 is! String) return false;

  int len1=s1.length, len2=s2.length;

  if (len1!=len2) return false;

  if (identical(s1, s2))

    return true;

  for (int from=0, to=len1-1; to>=from;) {

    if (s1.codeUnitAt(from)!=s2.codeUnitAt(from))return false; 

    if (s1.codeUnitAt(to)!=s2.codeUnitAt(to))return false;

    from++; to--;  

  }  

  return true;

}

It's slow like hell, but still faster by 25% than dart's built-in string compare.

If optimized, it will make small map as fast as java I think.

[Alex Tatumizer]

One correction: I mentioned DIV by prime in the context of java implementation of HashMap.

For one thing, memory didn't fail me (which is a good sign) - indeed, in the source of HashMap of java 1.2 we find: 

static final int DEFAULT_CAPACITY = 11;

(with new size set to old size *2 +1 in rehash).

But somewhere along the way, they changed implementation, and now DEFAULT_CAPACITY is 16, and it always set to power of 2, so division is gone.

Sorry for confusion.

[Mehmet D. Akın]

Hi Alex,

I slightly changed your code : https://gist.github.com/mdakin/db6e0b780ccd11ea0b8b

And run benchmarks: https://gist.github.com/mdakin/12d9ac332f2cf5abfa46 

(on a beefy Intel i7 machine)

Your small map implementation is always faster, usually >%40 and up to 2x faster. especially lookups. 

I think this looks promising, small maps are very common, and it is a good idea to optimize them. (I wonder if we can instrument maps for all of dart and see if this theory holds in real life, a histogram of size of hash maps would be useful)

For some maps, usually only a small portion of keys accessed, again, -if this assumption is correct-, a simple move to front scheme could improve performance further. Something like this:

 int _findIndex(hashCode) {
    int i=0;
    while (i<currentSize) {
      if (hashCodes[++i] == hashCode) break;
    }
    if (i < currentSize) {
      if (i > 0) {
        int t = hashCodes[0];
        hashCodes[0] = hashCodes[i];
        hashCodes[i] = t;
      }
      return i;
    }
    return -1;
  }

- Another idea is to use a sentinel to eliminate loop branch control. 

Thanks. 

Mehmet

[Alex Tatumizer]

Hi Mehmet,

I think the scenario where every key is accessed is more common, especially in case of json coming from the wire: we parse the string into json, then check every parameter.

Your implementation always puts last accessed key into 0-th position, which optimizes for the case "if key is accessed, then there's high probability the next read will access the same key again". Not sure this is common and is worth optimizing for, but I can be wrong. 

But that's a minor point really.

I spent some time trying to figure out why java is so fast. Indeed, it allocates Entry for each key-value. How is it possible to allocate so many objects without incurring prohibitive overhead of GC?

Here's the trick. Java is "cheating". My test case where I discarded the map after each iteration makes it prone to trickery with generational GC and whatnot, so the results are not representative for more general case.

If you hold your maps for some time, instead of discarding them immediately, java's performance takes a huge hit.

The thing slows down x2, or x3, in one case I managed to get x10, and in one case I got something that looked like hanging. But SmallMap, in the same situation, performs as if nothing had happened.

So in reality, for sizes less than 16 or so, SmallMap is faster not only against dart's generic map, but also against java's, and depending on scenario, it might be faster by much more than 40%.

Switching to a bit different topic.

Having fast, memory-efficient small maps, in principle, makes it possible to use these maps as common denominator in all kinds of serialization.

Which justifies the technique of providing handwritten toJson()/fromJson methods in class. 

Any other encoding can be implemented easily is you have map as input instead of object. Because producing (intermediate) small map is fast, it won't hurt overall performance that much. And in a case of json encoding, this map is already a json.

Maybe we don't really need any serialization "framework" after all, beyond toJson/fromJson?

[Alex Tatumizer]

Forgot a couple of other points that I wanted to mention

1) SmallMap is in fact LInkedHashMap; keys() iterator returns keys in the order of insertion. It might be handy! (Reordering last accessed kills the feature; BTW, when you reorder hashCodes, you have to reorder keys and values, too, otherwise the index is incorrect).

2) In java, there's String method intern() which includes your string into static HashMap of string constants. I think this method does too much.

What I'd prefer to have in dart is a method like String.xxxxx(str)  [ not sure about the name] with the following description:

if str is equal to some constant string, returns this constant string. Otherwise just returns str.

To make it fast, dart has to be able to figure out whether str is ALREADY a constant string. e.g. str.isConstantString();

3)  There's an issue already open that proposes syntax like ##arg, which is a sugar for "arg". Might be quite handy when you create Jsons, e.g

   var priceDollars=100;

   map.put(##priceDollars, priceDollars).

It can be supported by Editor, so when you rename priceDollars to priceInDollars, it will automatically change string.

[Alex Tatumizer]

Added java implementation of SmallMap (same algo as in dart)

https://gist.github.com/tatumizer/2f8dd726529101d559c4

And what do you think?

Java version still outperforms dart, even on constant strings (that is, slowness of String == in dart is not in play).

It outperforms dart by the same margin as before: about 25-30% (I still have to test on a better comp though, to be sure).

It's worth noting  that java version of SmallMap (in contrast with java.util.HashMap) doesn't exhibit any slowdown in scenario where we hold the map after operation (see prior post). To its credit, dart version of SmallMap behaves nice, too. Still, on every test, java is faster by the same margin. Not that it's overly critical, but it would be good to know why.

[Lasse R.H. Nielsen]

On Sun, Mar 1, 2015 at 5:18 PM, Alex Tatumizer <tatu...@gmail.com> wrote:

Forgot a couple of other points that I wanted to mention

1) SmallMap is in fact LInkedHashMap; keys() iterator returns keys in the order of insertion. It might be handy! (Reordering last accessed kills the feature; BTW, when you reorder hashCodes, you have to reorder keys and values, too, otherwise the index is incorrect).

2) In java, there's String method intern() which includes your string into static HashMap of string constants. I think this method does too much.

What I'd prefer to have in dart is a method like String.xxxxx(str)  [ not sure about the name] with the following description:

if str is equal to some constant string, returns this constant string. Otherwise just returns str.

To make it fast, dart has to be able to figure out whether str is ALREADY a constant string. e.g. str.isConstantString();

Just one comment: The Dart language doesn't have any notion of compile-time constant at runtime. At runtime, there is no feature that distinguishes an object originating from a compile-time constant expression from one originating from a "new" instantiation.

The VM might internally keep track of whether something is const, but that's an accident of implementation.

A valid implementation of compile-time constants for, e.g., dart2js would be to create one (lazily initialized!) global final variable for each compile-time constant value in the source code, and only create the value when it's first accessed. That is, compile-time constants can be desugared into final variables, which shows that there need not be any way to distinguish a "constant" value.

 

3)  There's an issue already open that proposes syntax like ##arg,

How cpp :)

 

which is a sugar for "arg". Might be quite handy when you create Jsons, e.g

   var priceDollars=100;

   map.put(##priceDollars, priceDollars).

It can be supported by Editor, so when you rename priceDollars to priceInDollars, it will automatically change string.

/L

[Kevin Millikin]

On Tue, Mar 3, 2015 at 9:44 AM, 'Lasse R.H. Nielsen' via Dart Misc <mi...@dartlang.org> wrote:

On Sun, Mar 1, 2015 at 5:18 PM, Alex Tatumizer <tatu...@gmail.com> wrote:

Forgot a couple of other points that I wanted to mention

1) SmallMap is in fact LInkedHashMap; keys() iterator returns keys in the order of insertion. It might be handy! (Reordering last accessed kills the feature; BTW, when you reorder hashCodes, you have to reorder keys and values, too, otherwise the index is incorrect).

2) In java, there's String method intern() which includes your string into static HashMap of string constants. I think this method does too much.

What I'd prefer to have in dart is a method like String.xxxxx(str)  [ not sure about the name] with the following description:

if str is equal to some constant string, returns this constant string. Otherwise just returns str.

To make it fast, dart has to be able to figure out whether str is ALREADY a constant string. e.g. str.isConstantString();

Just one comment: The Dart language doesn't have any notion of compile-time constant at runtime. At runtime, there is no feature that distinguishes an object originating from a compile-time constant expression from one originating from a "new" instantiation.

This is waaay off topic, but is that completely true?  The function 'test' below can distinguish between 'new Pi()' and 'const Pi()' on both the VM and dart2js:

class Pi {

  final double value = 3.14159;

  const Pi();

}

test(Pi pi) {

  print(identical(pi, const Pi()));

}

[Lasse R.H. Nielsen]

It identifies that "const Pi()" is identical to "const Pi()", but there is no way any code that doesn't already have a version of "const Pi()" can distinguish the two objects "const Pi()" and "new Pi()". There is no inherent property of the const object that makes it differ from any other instance.

 

You can desugar the program into:

final constPi = new Pi();

class Pi {

  final double value = 3.14159;

  const Pi();

}

test(Pi pi) {

  print(identical(pi, constPi));

}

(and replace "const Pi()" with constPi everywhere else in the program - it's a whole-program transformation).

The transformed program will be equivalent to the original in all ways, and it has *no* const objects.

If there was a way to distinguish an object that was created using a compile-time constant expression from one that wasn't, then it would be possible to write a program where the above transformation would not preserve semantics. I claim that it's not possible.

That is, the only way to identify const objects is to already know all the const objects, and see if an object is identical to one that is known to be const.

[Alex Tatumizer]

Checked dart SmallMap vs java SmallMap (equivalent implementation) on a better comp (core i7, 2.7Ghz), performance is the same. Sorry for falsely accusing compiler.

Average operation (put, get) time is about 10 nanosec.

Which is, when we reuse same strings as keys, so hashCode is cached and never recalculated
.

If we every time generate new copy of a key (as it happens, say, in json parsing), then hashCode overhead dominates.

In dart (if my calculations are correct) hashCode costs about 1.3 nanosecond PER CHAR. Isn't it too long?

[Mehmet D. Akın]

Hi,

Did you looked Observatory results? I added this custom tags to see a little bit detail (https://gist.github.com/mdakin/01aa816093a9259513c6) , and looks like ~30% is spent in linear search, ~25% in equals and ~6% in hashcode. Rest were cost of instrumentation and iteration loops etc. 

I don't know the underlying constraints, but If possible, making equals faster (at least for Strings, the most common key type) would make sense.

Also, Even if it is not cached for keys, I don't think hashCode costs 1.3 ns per char.

Mehmet.

[Alex Tatumizer]

6% on hashCode is due to the String caching of the hash (what a tongue-twister!).

I wrote specific test for hashCode of a new String, it shows 1.3 nanos per char.

It's easy to reproduce:

write 2 functions (assuming var randomString="alskdalskdjalksjd");

in one, execute x|=randomString.substring(1).hashCode in a loop

in another, execute x|=randomString.substring(1).length in a loop

Subtract one from another.

For equality - sure, String== is very slow. Maybe at some point dart will implement intrinsic. It can be done as a single processor command using SIMD. But even without SIMD, it can be made much faster. Right now it simply compares 1 char at a time.

For observatory: I tried, but found the interface clunky, didn't enjoy the look and feel. Probably  a work in progress. The idea is good though. Artistic quality is lacking.

[Mehmet D. Akın]

[...]

For observatory: I tried, but found the interface clunky, didn't enjoy the look and feel. Probably  a work in progress. The idea is good though. Artistic quality is lacking.

I think it is not bad, Just added a few tags, selected "Pause isolate on exit" and click on CPU profile on observatory page thats all :)  It seems  John Mccutchan is still working on improvements for observatory, so check it out in upcoming releases. And maybe open a bug if you think UI needs improvements.

Also I messed with an idea to use last 2-3 bits of stored hashcodes as usage counter for keys and swapping with previous entry if its counter value is >=  previous one. But then again these arrays are too small and I don't think it matters much if n < 10, and decided not to waste time. I guess simpler is better for such a scheme.

[Alex Tatumizer]

It's possible to write more memory-efficient (and probably faster) implementation of a variant of SmallMap where many small maps share the same set of keys (not necessarily known at compile time). But it would make sense only if someone stores very large number of small maps in memory. Not sure I know a good use case for this.

[Mehmet D. Akın]

I created https://code.google.com/p/dart/issues/detail?id=22642 for small maps, I hope my description is correct, please feel free to add more information to the issue.

[Alex Tatumizer]

Yes!!! It was promptly ACCEPTED!

Which is unusual. Normally, the issue collects dust for a year or so and then declared "stale", .

But this one became an instant hit!

P.S. Though it's not that important, but I just wanted to mention that "Tatumizer" is not my name per se, but rather a name of my yet-to-be-written application that was supposed to generate piano solos in the style of Art Tatum. While opening account on github, I confused the input box for my name with the name of application, and then it was too late.

To make things worse, my original idea behind the application proved to be untenable  Over the years, I made several iterations, with mixed success, until I renamed the app, and now it's called TheGig. It exists exclusively in my imagination though, and may never materialize. If it does, I will let everybody know.. Sorry for misunderstanding :-) 

[Greg Lowe]

> It's possible to write more memory-efficient (and probably faster) implementation of a variant of SmallMap where many small maps share the same set of keys

This is starting to sound like hidden classes as implemented in Javascript VMs (Since Javascript objects are effectively just maps). A while back I remember seeing an example where V8 outperformed the Dart VM in code which had a large number of small maps. I wonder if that is still the case.

[Alex Tatumizer]

For what it's worth, here's a "typed" variant of small map:
https://gist.github.com/tatumizer/89f721bd9878c6048c71

It can be used in a situation when many small maps share the same structure (that is, have same set of potential keys).

You create it as new TypedMap("foo") where "foo" is a unique name identifying the structure (set of names).

There's no requirement for names to be known at compile time.

Not sure I know too many use cases, but anyway - this map saves a lot of space. It occupies just slightly more memory than normal object instance with same fields as members. Performance is slower than SmallMap by about 15% (you have to pay for savings in memory), but still much better than standard map.

Basically, this is a new incarnation of PigeonMap, but here the same result is achieved by simpler means, with less restrictions and less hassle.

[Alex Tatumizer]

@Lasse: I'm still trying to wrap my head around constant strings. 

If information about constness of string is lost, then GC will try to garbage-collect these strings. Apparently (I'm speculating here), some mechanism permanently marks them as "used" on individual basis (e.g. by making static final var out of each constant string), so GC will try to collect the uncollectable in vain. And references to const strings can be all over the place, so it's quite a bit of Sisyphean work for GC, no?

[Lasse R.H. Nielsen]

On Sun, Mar 8, 2015 at 4:28 AM, Alex Tatumizer <tatu...@gmail.com> wrote:

@Lasse: I'm still trying to wrap my head around constant strings. 

If information about constness of string is lost, then GC will try to garbage-collect these strings.

If they are unreachable, yes (or at least: possibly).

It's likely that something is keeping the constant alive, if nothing else, then the code that can create the constant when executed.

 

Apparently (I'm speculating here), some mechanism permanently marks them as "used" on individual basis (e.g. by making static final var out of each constant string), so GC will try to collect the uncollectable in vain. And references to const strings can be all over the place, so it's quite a bit of Sisyphean work for GC, no?

I haven't done the VM GC, so I can't say for sure how they implement it. 

It could be that the constant strings (including all non-interpolated string literals) are all stored in special pages that are never GC'ed. They could even be shared between isolates created using Isolate.spawn (but I don't think they are).

Or maybe they are simply kept alive by the code objects that create them, so if the code objects all die and the code creating the string will never be called again (that's *hard* to detect), then the constant can be collected.

I think you can assume that constant values are not collected, but some runtimes might be smarter than that.

[Alex Tatumizer]

> I haven't done the VM GC, so I can't say for sure how they implement it.

Hesitating to ask: who implemented GC then?

Another topic.

In the earlier post, I claimed that performance of TypedMap is 15% worse as a tradeoff for saving memory.

This is not true. TypedMap can be made faster than SmallMap, by using same device earlier employed by PigeonMap.

I'd like to remind the idea. We have 16 different hash codes. We can pick octet (8 bits) from each hash code (by applying shift:

(hashCode[i]>>k)&0xFF with some fixed k) There's a very good chance that all those 16 octets are different at least for one value of k.

Then we take 256-byte table which maps each octet directly to index, other entries being -1. Thus we avoid linear search altogether.

Too bad that we don't know good application for TypedMaps, so this lovely idea remains just an abstract construction.

E.g. if JSON was designed in such a manner that each map inside it came with type hint, we could use it.

Maybe there are other use cases, not sure.

[Mehmet D. Akın]

On Sunday, March 8, 2015 at 4:00:04 PM UTC+1, Alex Tatumizer wrote:

> I haven't done the VM GC, so I can't say for sure how they implement it.

Hesitating to ask: who implemented GC then?

Another topic.

In the earlier post, I claimed that performance of TypedMap is 15% worse as a tradeoff for saving memory.

This is not true. TypedMap can be made faster than SmallMap, by using same device earlier employed by PigeonMap.

I'd like to remind the idea. We have 16 different hash codes. We can pick octet (8 bits) from each hash code (by applying shift:

(hashCode[i]>>k)&0xFF with some fixed k) There's a very good chance that all those 16 octets are different at least for one value of k.

Then we take 256-byte table which maps each octet directly to index, other entries being -1. Thus we avoid linear search altogether.

I don't think allocating an extra 256 bytes lookup table for every map (these are tiny maps remember) justifies a dubious performance gain. Also the collision probablity for a 256 bucket hashtable with 10 elements is ~20%. This means 20% of the time map will fall back to standard map, and will have the extra cost of copying existing elements. So I think this is not worth it. Keeping it simple is the best approach. Btw, unrelated to this, compared to old hashmaps, these small maps with linear lookup are faster only up to 6 elements, in a way new compact map implementation regressed the performance of maps with few elements compared to previous version.

[Alex Tatumizer]

I was talking about TypedMaps, where many maps share the same structure. In this case, we have 256 bytes lookup table shared by  all instances of same type, that is, practically free.

Take 16 random values out of 256. What is the probability that among those you find 2 equal? Roughly, 1/2 (see http://en.wikipedia.org/wiki/Birthday_problem)

We make 31-8=23 attempts to choose 16 random values (one for different k).

The probability of failure in ALL attempts in the same as in the following: toss a coin 23 times. What is the probability of getting all heads?

I tested against compact hash (with a flag) a weeks ago. Results were the same as for old hashmap. (Unless I did something wrong)..

Compact hash map does less allocations, so it really benefits you via reduced GC load. But SmallMap has the same property.

 

[Mehmet D. Akın]

On Sunday, March 8, 2015 at 11:06:36 PM UTC+1, Alex Tatumizer wrote:

I was talking about TypedMaps, where many maps share the same structure. In this case, we have 256 bytes lookup table shared by  all instances of same type, that is, practically free.

I see , well that makes this a microoptimization of a special case.

 

Take 16 random values out of 256. What is the probability that among those you find 2 equal? Roughly, 1/2 (see http://en.wikipedia.org/wiki/Birthday_problem)

A small correction, I gave example of 10 in 256, which makes probability of collisions  actually 16% , and your example has 38%. But doesn't matter,  we have the idea..

[Kevin Millikin]

On Sun, Mar 8, 2015 at 4:28 AM, Alex Tatumizer <tatu...@gmail.com> wrote:

@Lasse: I'm still trying to wrap my head around constant strings. 

If information about constness of string is lost, then GC will try to garbage-collect these strings. Apparently (I'm speculating here), some mechanism permanently marks them as "used" on individual basis (e.g. by making static final var out of each constant string), so GC will try to collect the uncollectable in vain. And references to const strings can be all over the place, so it's quite a bit of Sisyphean work for GC, no?

I still don't think it's entirely correct to say that Dart has no notion of compile-time constant at runtime.  At least, that's not the way I would explain it.

As I pointed out upthread, the predefined function identical() can distinguish between constant and non-constant objects.  In the specific case of strings, constant strings are identical iff. they are ==, and non-constant strings are identical iff. they are 'the same object'.

That could be implemented in different ways.  You could set a bit on the string to say whether it is constant or not and then decide whether to use == in the implementation of identical().  Or you could put constant strings in a symbol table and canonicalize them.  In the first implementation, there is a difference between constant and non-constant strings at runtime because one has the constant bit set.  And the second implementation is indistinguishable from the first.

[Lasse R.H. Nielsen]

I think this line of reasoning is breaking the "identical" abstraction. Arguably, so does the specification in its treatment of identical.

The way I prefer to see it, objects have identities (which is what traditionally distinguishes an object from a struct), and identical tests whether two references point to the same object.

The spec requirements on compile time constants are not saying that identical should cheat, but that equivalent compile-time constants should evaluate to the *same* object at runtime.

That also means that *all* number objects are canonicalized - there is only one instance of 42 ever - and that compile-time string expressions with the same content all evaluate to the same string object.

I agree that this is not what the specification says. It instead lists a number of cases where compile-time constants are identical (which are required because identical(a, b) can be a compile-time constant expression), and ends with "or ... c1 and c2 are the same object".

The fact that there may be more than one number object with the same value in the heap, or even multiple string objects with the same content that must compare identical, is an implementation detail (or even an implementation hack) which the specification was deliberately written to allow, but it's not a requirement. 

The language specification does not have any part of it that requires, or allows, distinguishing the value of a compile-time constant expression from a non-constant value at runtime by looking only at the object.

You can check whether a string value is identical to one originating from a compile-time constant expression, but that's not an inherent property of the string.

Implementing compile-time constants by rewriting the program to have compile-time constant expressions instead read the value from a lazily initialized global variable (only creating the value when the variable is first read) will also create an program that is indistinguishable from the original - and it won't have any compile-time constants at all [2]. Being equivalent to not being constant is pretty much the same as "being constant isn't a detectable property of the object".

I guess this all means that the specification isn't really picking a side, and since we can both keep reading it to match our way of looking at it, it's probably not even important. :(

/L 

[1] That needs access to the special classes used for constant List and Map literals, but for the remaining 

[2] Except that some places in the syntax only allows compile-time constants, so the rewrite has to be smarter for default parameter values and switch cases, and will probably never work for annotations.

[Kevin Millikin]

On Mon, Mar 9, 2015 at 11:29 AM, 'Lasse R.H. Nielsen' via Dart Misc <mi...@dartlang.org> wrote:

Implementing compile-time constants by rewriting the program to have compile-time constant expressions instead read the value from a lazily initialized global variable (only creating the value when the variable is first read) will also create an program that is indistinguishable from the original - and it won't have any compile-time constants at all [2]. Being equivalent to not being constant is pretty much the same as "being constant isn't a detectable property of the object".

And yet I claim that it must be some property of constant objects that makes such a rewrite correct.  Because it's not correct for non-constant objects.  :)

[Alex Tatumizer]

> You could set a bit on the string to say whether it is constant or not and then decide whether to use == in the implementation of identical().  Or you could put constant strings in a symbol table and canonicalize them.

Apparently, current implementaiton uses the latter approach. When I run performance test for identical("foo","foo"), it returns in no time (<1ns). Obviously, no real string comparison takes place here. Which indicates canonicalazed strings are in play.

So, it seems that String can easily provide method "str.isConstantString()", right? This could be helpful to avoid keeping 100000 instances of string "firstName" when we receive 100000 JSON objects {"firstName": "John"}. I would argue then

that while parsing JSON, calling key=String.tryGetCanonicalizedCopy(key) before inserting into map might help save space reduce GC load.

(With TypedMap, problem is solved differently: each "type" has its own canonicalization of every key is uses).

[Daniel Andersson]

Constant literals are allocated in the old generation at compilation time and are kept alive by references from Code objects (you can see this in the Observatory by tracing a retaining path for such a constant). Placing them in the old generation means they are infrequently visited by GC, but yes, they are still repeatedly marked/unmarked. Some language-wide constants, like true and false, reside in the shared, read-only "VM heap", where all objects permanently have its mark bit set, allowing the GC to ignore them completely. In general, we'd like to move more (likely) immortal objects to this VM heap. Other low-hanging fruit in terms of improvements for constants includes (non-small) maps: http://www.dartbug.com/7559

[Alex Tatumizer]

The game of the century: Linear search vs Binary search in Int32List!
Results will be published in 1 hour.
Place your bets!

[Greg Lowe]

https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/

[Alex Tatumizer]

> https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/

Monumental study indeed.

Mine is more modest. I'm testing pure dart, no SSE-optimized code, no deep unrolling.

Bottom line is: break-even for dart is roughly 24 (I'm testing average time - that is, if array contains [1,2,3... 24], I'm calling search for 1, 2, 3 ... 24 and average the results).

My processor is very close to the one used by the above study (i7, 2.7 GHz).

At break-even size 24, average timing for one search is about 10 nanoseconds.

Which is approximately equivalent to 0.45 array elements processed per clock cycle (vs 1 for C program, if I'm not mistaken). Which is not bad for dart compiler, considering the circumstances!

For some reason, SSE instructions are not utilized by libraries yet, or else we would have performance close to C (e.g. linear search corresponds to library method IntList32.indexOf, which is there, but not optimized at all).

NOTE: Though break-even is 24, the curves are close for bigger values - e.g. there's only 15% difference for size 32.
Code

int findIndexByLinearSearch(array, value) {
    for (int i=0, j=array.length-1; j>=i; i++, j--) {
       if (array[i]==value) return i;
       if (array[j]==value) return j;
    }
    return -1;
}
int findIndexByBinarySearch(sortedArray, value) {
    int lo = 0;
    int hi = sortedArray.length - 1;
    if (hi < 0) return -1;
    // looking for value in [lo..hi]
    while (lo <= hi) {
      int mid = lo + ((hi - lo) >> 1);
      int diff = value-sortedArray[mid];
      if      (diff <0) hi = mid - 1;
      else if (diff >0) lo = mid + 1;
      else return mid;
    }
    return -1;
}