Page 1 of 1
Fast accessing maps
Posted: Tue Sep 12, 2023 7:00 am
by jacdelad
Hi #PB_All,
due to a currently ongoing discussion about maps I decided to take a look at the help, which raised two questions:
Firstly, the help states
Once an element as been accessed or created, it becomes the current element of the map, and further access to this element can be done without specify the key. This is useful when using structured map, as no more element lookup is needed to access different structure field.
Does this mean that
Code: Select all
Cars("Ferrari F40")\Weight = 1000
Cars()\Speed = 320
Cars()\Price = 500000
is faster than
Code: Select all
Cars("Ferrari F40")\Weight = 1000
Cars("Ferrari F40")\Speed = 320
Cars("Ferrari F40")\Price = 500000
?
Secondly, I can define how many slots are preoccupied/predefined on creation. Can I change that afterwards, like redimming an array? I know that I simply can add as many elements as I want to, but from how I understand it, it should be faster to preoccupy more slots beforehand, if that's possible.
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 7:12 am
by wilbert
jacdelad wrote: Tue Sep 12, 2023 7:00 amDoes this mean that ... is faster than ... ?
Yes, the first approach is a lot faster.
jacdelad wrote: Tue Sep 12, 2023 7:00 amSecondly, I can define how many slots are preoccupied/predefined on creation. Can I change that afterwards, like redimming an array?
No, you can't change that.
A map uses a (hash) function on the key you pass to find out in what slot it has to be placed.
Changing the amount of slots afterwards would require every existing key inside the map to be processed again to find out to what new slot it should be moved.
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 8:26 am
by AZJIO
We had a discussion about
what a slot is. The number of slots does not limit the number of card elements. Is this some kind of cache with which a preliminary search is done? For example, we take every tenth or every hundredth element and its position, and when searching, we find a slot whose hash is greater than the one we are looking for, and the previous one is less, and then we search inside a certain area?
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 10:02 am
by Demivec
AZJIO wrote: Tue Sep 12, 2023 8:26 am
We had a discussion about
what a slot is. The number of slots does not limit the number of card elements. Is this some kind of cache with which a preliminary search is done? For example, we take every tenth or every hundredth element and its position, and when searching, we find a slot whose hash is greater than the one we are looking for, and the previous one is less, and then we search inside a certain area?
A 'slot' is a distinct result of a hash function. The default of 512 slots means that only 512 distinct values will result from hashing any value (only strings are currently possible as map keys).
If more than one element is added to the map and they have different keys that result in the same hash then they will form an effective linked list at that hash slot value. This means that when the map is searched to see if a key is present that the key is first hashed to see which slot to look in and then each value in the list at that slot is checked for a matching key.
Fewer slots will result in longer lists at each slot. This will result in more interations through elements at each slot each time elements are searched, added or deleted.
A rough estimation of the memory space needed for the structure of a map is a list element structure consisting of three pointers (*mapElement, *previousSlotEListlement, nextSlotListElement) for each slot plus an identical structure for each element linked into the same slot. ElementsCount * (ElementSize + SlotListElementSize) with no less than (SlotsCount * SlotListElementSize) being used regardless of ElementsCount.
I haven't done any empiracle memory tests to see how close these estimates correspond with reality but I am confident they are reasonably close. I will test them when I am able to. I believe others have done similar estimations in the forum before.
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 11:29 am
by benubi
I would expect the first version to be faster, because in the second approach the hash-value will be calculated 3x, when in the first it is 1x and then the current element is used 2x as a shortcut (without comparing hash values or calculating it).
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 12:30 pm
by NicTheQuick
benubi wrote: Tue Sep 12, 2023 11:29 am
I would expect the first version to be faster, because in the second approach the hash-value will be calculated 3x, when in the first it is 1x and then the current element is used 2x as a shortcut (without comparing hash values or calculating it).
Exactly. And that's what the help page talks about.
Of course this method only works either with only one single thread using the map at all times or when protecting the map with mutexes.
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 12:59 pm
by jacdelad
Oh, that's some light on the topic. I would expect the first approach to be faster too, or at least not slower. I'll have to change some of my programs, I never thought about that.
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 1:15 pm
by wilbert
jacdelad wrote: Tue Sep 12, 2023 12:59 pm
Oh, that's some light on the topic. I would expect the first approach to be faster too, or at least not slower. I'll have to change some of my programs, I never thought about that.
You are all right.
I answered the question with yes but made a mistake in typing second instead of first.
Of course the FIRST approach is the faster one.
Re: Fast accessing maps
Posted: Tue Sep 12, 2023 1:59 pm
by jacdelad
Ah ok. Thanks for clearing up.
