Enhancement request: (owned) key/string value deduplication

[ewaldc]

• Problem: large JSON strings that contain many keys with the same name (repeatative structures) consume a lot of memory as each key name is stored multiple times.
• Enhancement suggestion: deduplicate owned keys (and if that works eventually owned variant string values) during deserialization.
  Preliminary code on v6 and running code on v5 suggests it can save up to 25% of consumed RAM.
• Target platform: embedded systems with limited RAM memory e.g. ESP8266

I have tried to implement this myself here using two different approaches (see source code) but both seem to have the same erroneous effect: when you serialize the JSON document after deserialization, the tail elements of the JSON string seem to have gone missing (even though the serialized JSON string is semantically correct).

So far I have not figured out why. Although the code only returns a pointer to a previously allocated string in the _string pool (left side of the buffer, if one can be found) it somehow changes the slot/collection structure :-(.

On my modified 5.x version which implements a relocatable slot structure allowing for pre-parsed JSON strings to be stored in flash, it works OK. In that code the strings are stored in Flash, while the structure is copied into RAM.

Thanks in advance.
Ewald

[bblanchon]

Hi Ewald,

This feature that I call "string interning" has been on my road map for years.
Unfortunately, I cannot add it to v6 because I have no efficient way to access existing strings, and adding a list would affect the size of the memory pool.
Sure, it will save a lot of RAM when there are many duplicates, but it will slightly increase RAM usage when there are not.
I think it's an acceptable compromise, but I cannot do it without bumping the version number.

Best regards,
Benoit

[ewaldc]

Hello Benoit,
Thanks for the quick reply. Both approaches I implemented are indeed very unsophisticated, which has pro's and con's.

• approach one iterates over the string pool at each string insert. This one can not distinguish between keys and value strings (all or nothing approach)
• approach two recursively descends the JSON structure (as in serialize) and searches that way for a duplicate key. This method can separate keys from values, so it's possible to restrict it to keys only.

Code-wise both approaches are very dense (less than 100 bytes) and can be compiled out. They don't increase RAM space either. On v5, I implemented it as an argument to parse() so you can choose for which JSON strings to enable dedup or not.
In this way it's possible to select for each deserialization whether it's worth the extra execution time e.g. based on the source of the data (e.g. IOT data with repetitive key structures) or its size compared to the size of the available memory.
No way perfect, but IMHO reasonable:

• no code, execution or runtime memory increase when not compiled in
• very minor code increase when compiled in but no RAM increase and slight execution time increase at deserialziation only but only for desired JSON strings. I will dig up the execution time measurements I did last year of deserialize/parse with and without dedup for big and small strings.

Fully understand it requires a major version number. I was only trying to port my v5 version and understand whether it's a useful idea.
The problem is though that it does not work on v6. Maybe you have an idea where it goes wrong.

[bblanchon]

I like the idea of blindly scanning the memory pool as you did in your code.
I thought the fact that raw strings (see serialized()) are not null-terminated would be a problem, but you made me realize that ignoring the string boundary would work.
This means we can implement this feature without changing the storage and, therefore, include it in v6 👍

However, we can probably use a Boyer-Moore algorithm to speed up the search.

[ewaldc]

Ah, I was not aware of Serialized() (did it exist in v5?) 😌. Boyer-Moore is an excellent idea, had looked to that since it's part of the std library in C++17, just lacked the time to code it.
For me the bigger issue is that somehow it does not work in v6. When issuing serialize after deserialize, the final JSON objects/arrays are either missing or reduced in size and I have not found why 😕.

[ewaldc]

As promised the result of the performance impact tests for v6 on ESP8266 12E, 80MHz clock, using simple subtraction of millis() calls before and after (includes time lost due to WDT/yield() etc.). Average of 100 runs.

• JSON 1 - deserialize - regular: 25469 bytes memory use, 19 ms- dedup: 18521 bytes memory use 18521, 33 ms
• JSON 2 - deserialize - regular: 49870 bytes memory use (actually runs out of memory without stripping part of the code), 27 ms - dedup: 36780 bytes - 46 ms

So there is a significant ~75% performance hit on deserialize (but nowhere else) for a (mere) ~25% memory gain. However, ~50ms to parse the largest possible JSON string that fits in memory for an ESP12E is a very acceptable figure, hence why I decided to implement it in the most simple way (more accurately: use the lazy approach).

If there is interest, I am happy to share some of the other enhancement ideas implemented on v5 and see if I can port them to v6 (as a proof-of-concept):

• fixed size slot structure (~50% less memory use on ESP8266, removal of "empty" array/object slots, removal of collections)
• relocatable slot/string pool structure using relative offsets/pointers versus absolute ones (e.g. allowing for storing pre-parsed Json in flash/disk)
• mixed flash/RAM slot/string pool (useful but design needs rethinking, possibly too complex for v6)
• shared string (key/values) pool (between JsonDocuments)
• variable (character of choice) or no string terminators (I noticed you have that also in v6)

These are things I needed for my application where (IOT) Json strings can up be ~60K in size e.g. when communications get interrupted and the master ESP can not read out the slave ESP in time. ArduinoJson (v5 at the time) was by far the most modular object oriented implementation where it was possible to modify/enhance classes without breaking the whole code.

Will need to do some work on documentation and my C++ skills. As a hardware designer/kernel programmer (C), my code often looks more like a Linux kernel 😞

[ewaldc]

Finally managed to find some time to port my v5 enhancements to v6. It serializes/deserializes correctly a very large JSON string. On Windows 10 64 bit (and ESP) the JsonDocument size is about 35% smaller without string dedup (basically the VariantSlot structure is half the size) and 50%+ smaller with key/string value dedup. There is a main.cpp test program

You can find the code here.
In the quick port is included:

• Compact VariantSlot structure (50% size), all AllocRight is fixed size
• Relocatable MemoryPool, shrinkToFit does not need to move pointers (most of the time)
• Pre-enablement for pre-parsed JsonDocuments (e.g. stored in flash or filesystem), shared String pool
• Owned and external strings and raws

Not (yet) ported:

• Implement relocatable Strings using offsets (does not provide many benefits really, except for 8 string terminators of choice and ability to point to strings in const Json strings)
• String/Key dedup
• Pre-parsed JSON stored in flash or filesystem, shared String pool
• Linked JsonDocuments/memory pools (via Linked Array/Object's and linked MemoryPool). I found this to reduce memory fragmentation on ESP by extending the JsonDocument on an external/secondary memory pool, rather than trying to grow the buffer capacity.
• Auto-sized DynamicJsonDocument
• MemoryPool redesign (one VariantSlot pool, multiple string pools)

In principle all v6.x functions should work without changes.
Biggest code changes compared to standard AJ v6.x:

• VariantSlot/VariantContents
• memory pool must be passed to a number of classes (e.g. Serializer, MessagePack, ...)
• additional functions in MemoryPool.hpp to deal with offsets versus pointers
• dropping Positive/Negative integers (UInt becomes signed) --> very large integer data is more rapidly converted to float
• root VariantSlot moved from JsonDocument to pool (JsonDocument only contains the pointer)
• some limitations on JsonDocument sizes on embedded platforms e.g. on ESP: while JSON strings that are 2x bigger than current max can be successfully parsed, the largest VariantSlot offset is 32K. In extreme conditions, this might cause problems e.g. inserting an extra element to the very first object/array in a very large JSON document. This can be resolved by using linked memory pools.

To do

• Run/test all AJ test suites/ examples

It's merely a proof-of-concept to see if some enhancements created for v5 could be made to work on v6, a master piece of cpp code, extremely flexible/extendable but a bit more complex to change at the core for a C/kernel programmer.

The major driver for these enhancements is really the struggle with small RAM size of ESP/Arduino systems for IOT application, hence the focus on reducing memory and store more strings/data in flash and/or shared storage pools. Creating a relocatable memory pool and string/key dedup seemed to achieve to most bang for the buck.

Hope this gives some enhancement ideas for future versions and how these could be potentially implemented.
Ewald

[bblanchon]

Hi Ewald,

Thank you very much for sharing these improvements 👍

However, this thread has become a potpourri of improvements and it's overwhelming 😓
The changeset is so big, it's impossible to review; please make the information more digestible.

Let's use this issue to track the string deduplication only (you can see my progress on branch issue1303.
Please open more issues if you want to see the other features integrated.

Most of these changes were already in my (secret) backlog and some of them where even implemented in v6.6.
Remember that I had to roll them back because the impact on AVR was unacceptable.
Finding the right balance between 8-bit and 32-bit microcontrollers is a difficult task.

Lastly, it's one thing to make a prototype, but it's another to have it fully implemented, tested, and optimized.
So don't worry if it takes me a lot more time to implement these changes.

Anyway, thanks again for sharing these improvements; I'll do my best to integrate them.

Best regards,
Benoit

[ewaldc]

Sorry for the flood of information, it was with good intentions...
Agreed to keep focus solely on key/string dedup. Will give the branch a try and report back on findings.

That said, what I published is only one (but major) change: move to a relocatable (and hence more dense) MemoryPool. Will open a separate enhancement request for this and make sure that code only contains what is needed for that request.

Lastly, it's one thing to make a prototype, but it's another to have it fully implemented, tested, and optimized.
So don't worry if it takes me a lot more time to implement these changes.
You are so right on that one! Will try to test on AVR and make sure it passes all your tests and examples.

Regards, Ewald

[bblanchon]

This feature is available in ArduinoJson 6.16.0.