[dart-misc] How to do hard-coded mapping? Performance vs memory usage.

[Steven Roose]

Let's say I'd want a method that wants to return a new object instance from
a class depending on the input parameter (Strings f.e.). Consider a
situation in which there are a large number of maps required and only some
of them will be used (although very frequently).

There are several approaches for this:
https://gist.github.com/stevenroose/dc057850a9dbf8323bda

Now, the first is just if-else and is just to state the problem. It's not a
real option.

Then, there is one switch-based and two map-based approaches.

- HashMaps in Dart work constant time, that's great. However, the map
stays in memory as long as the Mapper class exists. I already mentioned
there will be a lot of these maps required, so that might not be what we
want.
Hence, time O(1), memory O(N)
- Switch on the other hand does not save anything in memory. However,
they work in linear time, which can be a lot slower when a large number of
items is added.
Hence, time O(N), memory O(1)

So how to evaluate these approaches? Is there a best-practice? At what
point is memory usage accepted to improve performance?


Better specifying the problem, it might be relevant to add that there
doesn't necessarily have to be a single mapping function, but the maps can
be divided into categories. F.e. mapHeadgear and mapFootwear. In this case,
the amount of memory needed is still O(N) for the map approaches, but the
time complexity for the switches changes to O(N/C) (with C the number of
categories).


Any thoughts?

Thanks!

['Andreas Kirsch' via Dart Misc]

Switches are also O(N) in memory. Memory is not just just data but also
code :)

Are you sure they are O(N) in time though? I could imagine the compiler
optimizing the code.

My guess is that a switch is faster than a map.

Post by Steven Roose
Let's say I'd want a method that wants to return a new object instance
from a class depending on the input parameter (Strings f.e.). Consider a
situation in which there are a large number of maps required and only some
of them will be used (although very frequently).
https://gist.github.com/stevenroose/dc057850a9dbf8323bda
Now, the first is just if-else and is just to state the problem. It's not
a real option.
Then, there is one switch-based and two map-based approaches.
- HashMaps in Dart work constant time, that's great. However, the map
stays in memory as long as the Mapper class exists. I already mentioned
there will be a lot of these maps required, so that might not be what we
want.
Hence, time O(1), memory O(N)
- Switch on the other hand does not save anything in memory. However,
they work in linear time, which can be a lot slower when a large number of
items is added.
Hence, time O(N), memory O(1)
So how to evaluate these approaches? Is there a best-practice? At what
point is memory usage accepted to improve performance?
Better specifying the problem, it might be relevant to add that there
doesn't necessarily have to be a single mapping function, but the maps can
be divided into categories. F.e. mapHeadgear and mapFootwear. In this case,
the amount of memory needed is still O(N) for the map approaches, but the
time complexity for the switches changes to O(N/C) (with C the number of
categories).
Any thoughts?
Thanks!
--
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

--
Why is this e-mail so short? Answer: five.sentenc.es.

[Alex Tatumizer]

Post by Steven Roose
Now, the first is just if-else and is just to state the problem. It's not

a real option.
If-else is, performance-wise, the same as switch (with current
implementation of switch in the language).

Switch can be faster than map only if the number of "cases" is very small,
under ANY implementation of switch. (BTW, one of possible internal
optimizations uses a map inside, when hardcoded heuristic tells it to do
so).

My advice: use single map for all mappings. Key should be an object {
String category; String name }. Override hashCode and ==. Cache hashCode in
the key object, to avoid calculating it every time. To compute hashCode,
use something like hashCode=(category.hashCode*31 +
name.hashCode)&0x1FFFFFFF

['Daniel Andersson' via Dart Misc]

Note that currently, *const* map literals are less efficient than non-const
maps:
https://code.google.com/p/dart/issues/detail?id=7559
I intend to fix this soon.

On Tue, Jun 2, 2015 at 8:23 AM, 'Andreas Kirsch' via Dart Misc <

Post by 'Andreas Kirsch' via Dart Misc
Switches are also O(N) in memory. Memory is not just just data but also
code :)
Are you sure they are O(N) in time though? I could imagine the compiler
optimizing the code.
My guess is that a switch is faster than a map.

Post by Steven Roose
Let's say I'd want a method that wants to return a new object instance
from a class depending on the input parameter (Strings f.e.). Consider a
situation in which there are a large number of maps required and only some
of them will be used (although very frequently).
https://gist.github.com/stevenroose/dc057850a9dbf8323bda
Now, the first is just if-else and is just to state the problem. It's not
a real option.
Then, there is one switch-based and two map-based approaches.
- HashMaps in Dart work constant time, that's great. However, the map
stays in memory as long as the Mapper class exists. I already mentioned
there will be a lot of these maps required, so that might not be what we
want.
Hence, time O(1), memory O(N)
- Switch on the other hand does not save anything in memory. However,
they work in linear time, which can be a lot slower when a large number of
items is added.
Hence, time O(N), memory O(1)
So how to evaluate these approaches? Is there a best-practice? At what
point is memory usage accepted to improve performance?
Better specifying the problem, it might be relevant to add that there
doesn't necessarily have to be a single mapping function, but the maps can
be divided into categories. F.e. mapHeadgear and mapFootwear. In this case,
the amount of memory needed is still O(N) for the map approaches, but the
time complexity for the switches changes to O(N/C) (with C the number of
categories).
Any thoughts?
Thanks!
--
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

--
Why is this e-mail so short? Answer: five.sentenc.es.
--
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

['William Hesse' via Dart Misc]

In the Dart language specification, it says explicitly: "The switch
statement should only be used in very limited situations (e.g., in-
terpreters or scanners)". It is true, it might be optimized, because
only integers, strings, and classes that don't override
Object.operator== are allowed as constants, but the semantics are
defined as a linear check of the cases in order.

In any case, the space taken by the switch statement's code and the
compiled versions of that switch statement will take plenty of memory.
Using maps
is much more efficient for the lookup for large switches, because maps
use hash values rather than linear search. And the map objects are
quite optimized in their memory usage - the keys and value pointers
might just use a machine word each in the map object, and the overhead
of hash maps could be a factor of 2, for example. The size of the
function objects (closures) that are the map values and strings used
as keys is much more than the map itself, probably.

The examples of _map3helper and _map4helper given in your sample code
are exactly equivalent. Static variables in Dart are initialized
lazily, so the static variable _map3helper is not given its value, and
the map object in its initializer is not constructed, until a function
first tries to read a value from the variable, just like the code for
_map4helper does explicity. This is true for both top-level and class
static variables.



On Tue, Jun 2, 2015 at 5:23 PM, 'Andreas Kirsch' via Dart Misc

Switches are also O(N) in memory. Memory is not just just data but also code
:)
Are you sure they are O(N) in time though? I could imagine the compiler
optimizing the code.
My guess is that a switch is faster than a map.

Post by Steven Roose
Let's say I'd want a method that wants to return a new object instance
from a class depending on the input parameter (Strings f.e.). Consider a
situation in which there are a large number of maps required and only some
of them will be used (although very frequently).
https://gist.github.com/stevenroose/dc057850a9dbf8323bda
Now, the first is just if-else and is just to state the problem. It's not
a real option.
Then, there is one switch-based and two map-based approaches.
HashMaps in Dart work constant time, that's great. However, the map stays
in memory as long as the Mapper class exists. I already mentioned there will
be a lot of these maps required, so that might not be what we want.
Hence, time O(1), memory O(N)
Switch on the other hand does not save anything in memory. However, they
work in linear time, which can be a lot slower when a large number of items
is added.
Hence, time O(N), memory O(1)
So how to evaluate these approaches? Is there a best-practice? At what
point is memory usage accepted to improve performance?
Better specifying the problem, it might be relevant to add that there
doesn't necessarily have to be a single mapping function, but the maps can
be divided into categories. F.e. mapHeadgear and mapFootwear. In this case,
the amount of memory needed is still O(N) for the map approaches, but the
time complexity for the switches changes to O(N/C) (with C the number of
categories).
Any thoughts?
Thanks!
--
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

--
Why is this e-mail so short? Answer: five.sentenc.es.
--
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

--
William Hesse

[Steven Roose]

First of all, thanks for all the responses!

This is interesting. I always figured that the code and the runtime
variables were stored differently and that code did't have so much of an
impact on runtime memory usage, especially in a scripting language like
Dart and (when compiled) JS.

So to summarize, it doesn't actually matter memory-wise, but
performance-wise, a Map is more efficient because switch and if-else search
lineariy.

@Alex concerning the hashcodes, it will most probably be strings, they have
good hashcodes.

Thanks again for the responses. Glad I learned something today :)

Post by 'William Hesse' via Dart Misc
In the Dart language specification, it says explicitly: "The switch
statement should only be used in very limited situations (e.g., in-
terpreters or scanners)". It is true, it might be optimized, because
only integers, strings, and classes that don't override
Object.operator== are allowed as constants, but the semantics are
defined as a linear check of the cases in order.
In any case, the space taken by the switch statement's code and the
compiled versions of that switch statement will take plenty of memory.
Using maps
is much more efficient for the lookup for large switches, because maps
use hash values rather than linear search. And the map objects are
quite optimized in their memory usage - the keys and value pointers
might just use a machine word each in the map object, and the overhead
of hash maps could be a factor of 2, for example. The size of the
function objects (closures) that are the map values and strings used
as keys is much more than the map itself, probably.
The examples of _map3helper and _map4helper given in your sample code
are exactly equivalent. Static variables in Dart are initialized
lazily, so the static variable _map3helper is not given its value, and
the map object in its initializer is not constructed, until a function
first tries to read a value from the variable, just like the code for
_map4helper does explicity. This is true for both top-level and class
static variables.
On Tue, Jun 2, 2015 at 5:23 PM, 'Andreas Kirsch' via Dart Misc

Post by 'Andreas Kirsch' via Dart Misc
Switches are also O(N) in memory. Memory is not just just data but also

code

Post by 'Andreas Kirsch' via Dart Misc
:)
Are you sure they are O(N) in time though? I could imagine the compiler
optimizing the code.
My guess is that a switch is faster than a map.

Post by Steven Roose
Let's say I'd want a method that wants to return a new object instance
from a class depending on the input parameter (Strings f.e.). Consider

a

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
situation in which there are a large number of maps required and only

some

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
of them will be used (although very frequently).
https://gist.github.com/stevenroose/dc057850a9dbf8323bda
Now, the first is just if-else and is just to state the problem. It's

not

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
a real option.
Then, there is one switch-based and two map-based approaches.
HashMaps in Dart work constant time, that's great. However, the map

stays

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
in memory as long as the Mapper class exists. I already mentioned there

will

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
be a lot of these maps required, so that might not be what we want.
Hence, time O(1), memory O(N)
Switch on the other hand does not save anything in memory. However,

they

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
work in linear time, which can be a lot slower when a large number of

items

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
is added.
Hence, time O(N), memory O(1)
So how to evaluate these approaches? Is there a best-practice? At what
point is memory usage accepted to improve performance?
Better specifying the problem, it might be relevant to add that there
doesn't necessarily have to be a single mapping function, but the maps

can

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
be divided into categories. F.e. mapHeadgear and mapFootwear. In this

case,

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
the amount of memory needed is still O(N) for the map approaches, but

the

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
time complexity for the switches changes to O(N/C) (with C the number

of

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
categories).
Any thoughts?
Thanks!
--
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

Post by 'Andreas Kirsch' via Dart Misc

Post by Steven Roose
To unsubscribe from this group and stop receiving emails from it, send

an

Post by 'Andreas Kirsch' via Dart Misc
--
Why is this e-mail so short? Answer: five.sentenc.es.
--
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

Post by 'Andreas Kirsch' via Dart Misc
To unsubscribe from this group and stop receiving emails from it, send

an
--
William Hesse