Bug in map ( and how to avoid it )

[argumentum]

expandcollapse popup

Global $g_iCount
Exit test()
Func test()
    Local $iCount = 0 ; should always be 0
    For $n = 0 To 99
        Main()
        If $iCount <> $g_iCount Then
            ConsoleWrite(' ' & $n & '(' & $g_iCount & ')')
            $iCount = $g_iCount
        EndIf
    Next
    ConsoleWrite(@CRLF)
EndFunc   ;==>test

Func Magic()
    $g_iCount = 0
    Local $this[]
    $this['c'] = 11
    If $this[8] Then $g_iCount += 1 ; ConsoleWrite('lol $this[8] = ' & $this[8] & @CRLF)
    Return $this
EndFunc   ;==>Magic

Func Main()
    Local $a
    For $i = 0 To 99 Step 1
        Magic()
        Dim $a = [0, 0, 0, 0, 0, 0, 0, 0, 0]
        $a = CopyToMap($a)
    Next
EndFunc   ;==>Main

Func CopyToMap($x)
    Local $m[], $1 = UBound($x, 1)
    For $j = 0 To $1 - 1 Step 1
;~      $m[$j] = $x[$j] ; bug
        $m[String($j)] = $x[$j] ; no bug
    Next
    Return $m
EndFunc   ;==>CopyToMap

The help file states this in regards to the map functions:
Warning: This feature is experimental. It may not work, may contain bugs or may be changed or removed without notice.
DO NOT REPORT BUGS OR REQUEST NEW FEATURES FOR THIS FEATURE.

Therefore, all we can do is avoid them. The code above shows such bug. The solution: name your maps with strings.

Ok, good chat

Note:  @Mars shared this in a chat at https://autoit.de/ . And I did not know of it. And probably neither did you. Now you do. 

 

[AspirinJunkie]

First, I pared down the script to the essentials:

For $i = 1 To 20
    ; create new(!) map, add one element to the string index "c" (which calculated position in the internal list is index 8)
    Global $m1[]
    $m1["c"] = 1

    ; check if there`s a value at the index 8 (shouldn`t)
    If $m1[8] Then ConsoleWrite($m1[8] & @CRLF)

    ; create another map and add value at the same integer index as the one $m1 checked
    Global $m2[]
    $m2[8] = 1
Next

I made the following observations:

1. It does not occur with all string indexes, but only with some. It is noticeable that each string index has a fixed associated integer index. If you use a different integer index, the phenomenon does not occur. So far, I have found the following combinations in which the phenomenon occurs:

| String-Index | Integer-Index | 
| ------------ | ------------- |
| "["          | 0             |
| "<"          | 1             |
| ""           | 5             |
| "c"          | 8             |
| "D"          | 9             |
| "%"          | 10            |
| "k"          | 16            |
| "L"          | 17            |
| "-"          | 18            |
| "s"          | 24            |
| "T"          | 25            |
| "{"          | 32            |
| "\"          | 33            |
| "="          | 34            |

These relationships can be explained well using hash index collisions.
AutoIt uses the DJB2 hash function in its maps. If you use this for the letters and then scale it to the table size using modulo, you get exactly the corresponding integer indices.
Only the table size is obviously not fixed, as the index sometimes fits for 32 elements and sometimes for 64.
For example: “c” has a DJB2 hash value of 177672. If we assume that the map in AutoIt has 32 elements at that point, the index for “c” is calculated as 177672 % 32 = 8.
This also works for the other string indexes. E.g., “D” --> 177641 % 32 = 9 or “” --> 5381 % 32 = 5.
Only the size of the hash table is obviously variable, as some fit for a size of 32 elements and some for 64.
However, thanks to the bug, we can learn a lot about the internal structure of AutoIt maps. They are DJB2-based hash tables that start with 32 or 64 elements.

2. This behavior only occurs when the map $m2 is created and an element is created with the same integer index as in $m1. If only this index is set, a match is reported very often. If other indexes are also set, the match does not occur as frequently.

One possible explanation for this behavior is as follows:

A hash table is essentially an array with a specific size. This size is fundamentally independent of the number of elements it contains (resizing makes sense but is not mandatory). In this case, a map is obviously initially populated with either 32 or 64 elements. When a value is added to the hash table, the hash value of the key is calculated and this calculated value is mapped to the array size using modulo. If the key is “c”, for example, the DJB2 hash (the hash algorithm used in AutoIt) is 177672.
To obtain an index for our array in the map, we have to reduce this hash value to the range 32 or 64. This is easy to do using the modulo operator. And with 177672 % 32, we get 8 as the result.
The value for the key “c” is therefore stored in the internal array at index 8.
However, since several keys could end up at index 8, we need to create a way to hold multiple elements there.
For each index, a list is created (a “bucket”) that contains all elements whose key matches this index.
The key and value of these elements are then simply stored one after the other in the bucket itself.
When a value is queried, the index is first calculated and then this bucket is traversed linearly to see if the specific key is contained in it.

In AutoIt, these buckets do not necessarily seem to be used only by one map instance.
At some point, two maps share a bucket, resulting in a phenomenon like the one we see here.
So you would have to take a closer look at the initialization of the map to see exactly where the problem lies.

 

[argumentum]

9 hours ago, AspirinJunkie said:

... The value for the key “c” is therefore stored in the internal array at index 8. ...

Nice dive into it @AspirinJunkie.

Since the help file states clearly that is "experimental" and basically "take it or leave it", would string only names have collisions ?, because if they don't, just avoiding integers ( that could be matching the index ) would solve the problem/bug, in using maps.

[AspirinJunkie]

4 hours ago, argumentum said:

would string only names have collisions ?

It seems that this is less about index collisions. The real problem is obviously that memory areas are being used across multiple map instances.
Whether this occurs exclusively when using string indices in conjunction with integer indices or in other cases as well, we cannot know here and now.
Without having the source code for the implementation, we can only speculate about what is happening in the background based on the behavior.

And so far, it seems to me that the memory areas for the buckets of the hash table are not completely cleaned up when dereferencing the map variable, and on the other hand, these areas are used when initializing a map variable without being fully prepared for use (e.g., memory area zeros or something like that).
There may well be a clever idea behind this, for example, to increase performance or something like that—we don't know.

However, the current implementation is undoubtedly a bug, and worse still, a bug whose consequences cannot really be assessed at present.
Therefore, we cannot simply dismiss the issue with blanket statements such as “don't use integer keys” or something similar.

This naturally raises the question of how to deal with it.
It has been clearly stated that bug reports should not be created for maps.
Nevertheless, the bug tracker is full of tickets for maps, and they are being processed as normal.
That's why I would have liked to discuss the whole thing in advance in the forum, preferably with the developers involved (actually, I wanted to do just that in the German forum first, but you had already posted the thread here...).
In my opinion, the “AutoIt General Help and Support” forum is not the right place for this, but rather “AutoIt Technical Discussion.”

However, it may well be that the bug has already been fixed and has been resolved in the course of the following ticket: https://www.autoitscript.com/trac/autoit/ticket/3948
The phenomenon described there is quite similar.

Edited 2 hours ago by AspirinJunkie