Closed Bug 1545732 Opened 6 years ago Closed 6 years ago

Add support for compressed strings

Categories

(Core :: XPCOM, enhancement)

enhancement
Not set
normal

Tracking

()

RESOLVED WONTFIX
Tracking Status
firefox68 --- affected

People

(Reporter: janv, Assigned: janv)

References

Details

Attachments

(1 file)

New local storage implementation currently uses standard nsString for storing values in memory. These strings can be sometimes really big (up to 5MB).
We would like to compress specific values (bug 1513937). There is SnappyCompressInputStream/SnappyCompressOutputStream, but that looks too heavyweight for storing individual values in local storage.

One option is to create a wrapper around nsString, but that would increase memory footprint in cases when compression is not needed. sizeof(nsString) is currently 16 bytes, adding any additional byte would align that to 24 bytes. There are some free bits in mDataFlags that could be used instead.

I've done some investigation and it seems that snappy compression of anything smaller than 16 bytes will always result in bigger data. So a new string class would check the size and skip compression for buffers smaler than 16 bytes.

The goal is to improve overall performance and reduce memory footprint and also mitigate crashes caused by failing SetLength() especially on 32 bit platforms.

Blocks: 1513937

Note that we don't plan to compress all values. Values that are stored in a content process for immediate access by JS wouldn't be compressed. However, all the changes done in a snapshot are currently buffered in an array which is then sent to the parent when the snapshot is checkpointed. Such values can be compressed, so we would reduce memory footprint in content processes and also send less bytes over IPC which should help with bug 1534222.

Assignee: nobody → jvarga
Status: NEW → ASSIGNED

Just to reiterate some wisdom from :bkelly on another bug: Snappy knows when it's unable to compress something, so any increase in size is effectively just the meta-data/framing indicating the thing can't be compressed. From a complexity perspective, it might make sense to just always use Snappy. (Looking at https://github.com/google/snappy/blob/master/framing_format.txt it might also be adding a CRC?)

Well, I did some experiments with small buffers and I don't think we want to use it for anything smaller than 16 bytes.

"xxxx" (4 'x' chars) "compresses" to 6 bytes
"xxxxxxxxxxxxxxxx" (16 'x' chars) "compresses" to 18 bytes
"xxxxxxxxxxxxxxxxx" (17 'x' chars) compresses to 8 bytes

Attached patch WIPSplinter Review

Nathan, would you approve a patch like this ?

Flags: needinfo?(nfroyd)

(In reply to Jan Varga [:janv] from comment #5)

Nathan, would you approve a patch like this ?

My initial inclination is that this sort of information belongs to the client of nsCString etc. and not the string implementation itself. (Compressed nsString also seems kind of weird, since compressed data is really more of a byte string rather than a char16_t string.) What's the benefit of having this in the string implementation versus just having SnappyCompress / SnappyUncompress routines that are analogous to the ToCompressed / ToUncompressed routines in the patch?

Flags: needinfo?(nfroyd)

Local storage uses unicode strings, so it must be nsString, any conversion to nsCString would add additional overhead.
The other thing is, that sometimes it's not efficient to compress the string, so we need to store the information/flag somewhere. I think the most efficient way is to use the free bits in mDataFlags.

The attached patch is just a first step, we can later implement storing of compressed strings in sqlite database and then distribute compressed strings to other content processes for the same origin. A content process would then uncompress it when it's needed.

We can also add telemetry later to collect data about compression efficiency, so we would get an idea what type of data is stored across the web which could be used for further improvements.

In other words, a process can directly read received strings if they are smaller than 16 bytes or compression didn't produce smaller buffer. This saves extra memory allocation.

(In reply to Jan Varga [:janv] from comment #9)

In other words, a process can directly read received strings if they are smaller than 16 bytes or compression didn't produce smaller buffer. This saves extra memory allocation.

I don't understand this comment. This comment pertains to "received strings" as in receiving them over IPC? Or received strings as in reading them out of the database? I'm not sure I see how a string flag makes this any faster than some off-to-the side flag.

I concede that an off-to-the-side flag would be larger than the proposed solution. I don't think that matters very much, though, and it makes it more likely that the LSNG code (or whoever else might use compressed strings of some kind) actually has to be explicit about what is or isn't compressed in the C++ type system, rather than a runtime flag, which seems like a desirable thing.

(In reply to Nathan Froyd [:froydnj] from comment #10)

(In reply to Jan Varga [:janv] from comment #9)

In other words, a process can directly read received strings if they are smaller than 16 bytes or compression didn't produce smaller buffer. This saves extra memory allocation.

I don't understand this comment. This comment pertains to "received strings" as in receiving them over IPC? Or received strings as in reading them out of the database? I'm not sure I see how a string flag makes this any faster than some off-to-the side flag.

I meant strings received over IPC. Saving extra allocation is one thing and for that we don't need direct integration in xpcom string module. I'm more worried about memory footprint. The extra information compressed/uncompressed needs to be stored somewhere, I can do that in a new C++ class, for example LSValue, but that adds at least one byte to every LSValue (there's also the issue with memory alignment which makes it even worse). There can be multiple copies of the same key/value pair. We keep all the pairs preloaded in the parent process. Database snapshots use them to save original values when database changes. Content processes lazily load them and they are also distributed across content processes to fire storage change events (old value and new value). So they exist all over the app.
An extra byte could easily defeat memory savings from compression in some situations or it could make it even worse.
If we use 2 free bits in mDataFlags, then there wouldn't be any extra memory requirement.

I concede that an off-to-the-side flag would be larger than the proposed solution. I don't think that matters very much, though, and it makes it more likely that the LSNG code (or whoever else might use compressed strings of some kind) actually has to be explicit about what is or isn't compressed in the C++ type system, rather than a runtime flag, which seems like a desirable thing.

I agree to some extent. It would be a bit cleaner, but it would also be less efficient from memory footprint point of view IMO.
As I mentioned above, these strings/values exist all over the app, so we should consider if "cleaner" code is more important than memory savings.

I can't think of any other consumer right now, but maybe later we would find other places in the code where compressed strings could be useful.

The performance team closely watches LSNG performance, so we need to pay special attention to issues like this :)
Seriously, I think this patch doesn't pollute the string module so much, but it's up to you to decide.

Maybe asuth can comment on this too, he is the main reviewer, he has great knowledge of LSNG.

I don't think the argument has been sufficiently made for integrating string compression into the string implementation/type hierarchy.

As I understand our LSNG implementation goals:

  • Strings are stored compressed on disk.
  • Strings are stored compressed in the parent process.
  • Strings travel in a compressed format over IPC.
  • Strings are decompressed in the child / content process. (Or same-process LSNG usage.)

It seems feasible for us to use a custom type and IPC serializer/deserializer so that we compress when writing in the to-parent direction and we decompress when reading in the from-parent direction. I think this nicely avoids duplicate memory storage, etc.

(I do understand that it's not the immediate plan to store the strings compressed in the database yet, but that's somewhat orthogonal to the IPC parent/child issue.)

But the issue is that local storage is often used as relatively small database with small values, so compression is not needed. It's definitely not needed for values smaller than 16 bytes. So a value can be stored uncompressed or compressed and that information needs to be saved somewhere.

I also don't want to automatically compress/decompress in IPC serializer, I want to have more control over it. For example some prefilled values in a snapshot may not be used. So it's better to decompress them on demand.

(In reply to Andrew Sutherland [:asuth] (he/him) from comment #12)

It seems feasible for us to use a custom type and IPC serializer/deserializer so that we compress when writing in the to-parent direction and we decompress when reading in the from-parent direction. I think this nicely avoids duplicate memory storage, etc.

Which duplicate memory storage ?

I can imagine an optimization for the storage DOM event.
The attributes oldValue and newValue would decompress lazily too.
I have no plans for that right now, it's just another example how integration with strings could be quite useful.

Ok, I found out that we can gain even bigger savings by storing values in UTF8 in the parent. For that, we need to store original UTF16 length as well. So a new C++ class is needed which will also contain the compressed flag.
Sqlite internally uses UTF8 and transparently converts strings when we load/store values. We can move this conversion to content processes and save memory at the same time.

I did some measurements in the meantime and it seems that compression doesn't have an impact on page load time (talos tp6 and raptor tp6).

Anyway, we could still try to add a compressed nsCString, but since there's no other client for that and we need to store more information about a local storage value (not just 2 bits), I'm resolving this as WONTFIX.

Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → WONTFIX
Component: String → XPCOM
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: