Add option to use HashSet and HashMap instead of default Set (LinkedHashSet) and Map (LinkedHashMap) about built_collection.dart HOT 11 CLOSED

+1. Maybe new types for existing entities instead of bool flag would be more suitable for me.

from built_collection.dart.

Let me see if I understand correctly. Updating a BuiltSet is done via a SetBuilder, which uses a LinkedHashSet internally.

So you're comparing LinkedHashSet to HashSet performance?

I believe they are both O(1) for insert/delete, but there is of course a difference in the constant. You're saying 1) you don't care about ordering, 2) the performance difference is important for you?

Could you maybe give more detail on what you're doing and the performance numbers you see in practice? It's definitely possible to provide unordered versions as an option, there just needs to be a clear use case where it makes sense.

Thanks!

from built_collection.dart.

Hi, @davidmorgan

1. We don't care about ordering of items at collection.
2. Performance is crucial for us.

We have a lot of elements > 10 000 that we must keep in memory at once.
We must track state of selected elements and keep rendering smooth and responsive.

If use HashSet - it takes 50ms for one operation.
If use LinkedHashSet - it take 100 ms for one operation.

So it would be extremely helpful that library gives ability to choose what to use to achieve best performance. Thanks!

from built_collection.dart.

One more question -- if you are frequently doing a small number of changes to the set, then the cost of rebuilding the set each time could be what's dominant.

If for example you always update and throw away the old set, you could try profiling by changing _safeSet to always return _set instead of sometimes copying:

https://github.com/google/built_collection.dart/blob/master/lib/src/set/set_builder.dart#L165

This breaks immutability, i.e. it makes the builder modify the current set instead of creating a new one. If this is the bottleneck then we should first address this problem.

from built_collection.dart.

Hi @davidmorgan

I have profiled compiled js code and have found that real performance bottleneck is _checkElement and _checkElements functions. If I remove those functions I will get almost the same performance with BuiltSet as with HashSet's. Just try adding many (> 1000) elements with add or addAll functions with those functions in place or removed.

from built_collection.dart.

Just a guess, code that throws exceptions is not optimized as well (by V8 at least).

from built_collection.dart.

Thanks for investigating!

Those checks are a legacy from before strong mode, when Dart gave very little help to make sure you put the right type elements in your collections. If you're using the analyzer with strong mode enabled then they add little value.

I plan on getting rid of them soon. I'll take a look.

from built_collection.dart.

I started looking at this; unfortunately it's likely to need breaking changes to the interfaces to get rid of the type checks. This still makes sense, but we'll have to do it carefully to make sure we get it right.

e.g. we'd need BuiltSet(Iterable iterable) instead of BuiltSet(Iterable iterable) -- so we can use the static checking to know that we don't need to check individual elements.

Something we could do easily would be to add a global flag to reduce checking. Right now we check for correct type and we check for nulls (because it can't have the correct type if it's null). I wonder if it would be fast enough if we just reject nulls and don't check the type -- would you mind measuring this?

i.e. instead of 'element is E' we just do 'element != null'.

from built_collection.dart.

I have checked that replacing _checkElement with this:

void _checkElement(Object element) {
  if (element == null) {
    throw new ArgumentError('invalid element: ${element}');
  }
}

increases performance by ~ 2x times.

It seems that null check is very fast and it doesn't affect performance at all.

from built_collection.dart.

Ah, that we can more easily change I think -- no need to change the signatures, we can just drop type checks on methods that explicitly take elements of the right type. I'll take a look. Thanks!

from built_collection.dart.

This PR removes all the checks that can currently be removed assuming you're using strong mode

#75

This should speed things up quite a bit!

from built_collection.dart.