literal storage: 4x performance improvement using a hashmap

[ronanj]

This PR is used to improve the literal storage performance:

Currently, literals are stored using a linked list: The drawback of the linked list is that when the number of literal entries increases, the time it takes to add a new entry increases proportionally to the number of entries: The reason is that before adding new entries, the storage engine first needs to iterate over all existing entries to find out if the "new" entry is a duplicate of an existing one or a new entity.

When running on a 200 Mhz CPU with a heap stored in PSRAM, if 1000 entries are already in the literal storage linked list, then it takes almost 1 millisecond to add a new entry (eg 1 millisecond to iterate over all existing 1000 entries). This makes loading snapshots very slow, especially when many background modules have already been loaded (where each background module adds its literals). Empirically, we measured that it takes 200 milliseconds for jerry_exec_snapshot to load and execute a snapshot containing about 200 literals when 1000 literals are already in the list before loading (measured on 200Mhz CPU with heap in PSRAM).

The change introduces an additional hashmap to speed up the look-up of existing literals: This way, it is not necessary to iterate through the entire literal linked list (in O(n)) - and instead, an O(1) lookup operation can be used. Empirically, we have noticed that the application that took 200 milliseconds to load now takes 50 ms (measured from jerry_exec_snapshot), bringing a 4 times performance improvement.

This feature can be enabled using the flag JERRY_LIT_HASHMAP. The test configuration has been updated to include this feature flag. Unit and functional tests have successfully passed. Test has also been done on the Open Harmony Jerry script version.

JerryScript-DCO-1.0-Signed-off-by: Ronan Jezequel ronan.jezequel@gmail.com

[ronanj]

ok, let me rewrite the hashmap library, and at the same time use the standard comment syntax from jerryscript.

[ronanj]

New commit added, with hashmap completely written from scratch - and also with better performance.

[zherczeg]

Looks like a nice patch! We check it further soon

[zherczeg]

It looks like tests/jerry/arithmetics.js fails. Do you know why?

[matetokodi]

@ronanj I apologize for the delay, the CI issues for OSX have been resolved, please squash and rebase your changes, and add DCO to the commit message.