• Leszek Swirski's avatar
    [runtime] Move string table off-heap · 1546be9c
    Leszek Swirski authored
    Changes the isolate's string table into an off-heap structure. This
    allows the string table to be resized without allocating on the V8 heap,
    and potentially triggering a GC. This allows existing strings to be
    inserted into the string table without requiring allocation.
    
    This has two important benefits:
    
      1) It allows the deserializer to insert strings directly into the
         string table, rather than having to defer string insertion until
         deserialization completes.
    
      2) It simplifies the concurrent string table lookup to allow resizing
         the table inside the write lock, therefore eliminating the race
         where two concurrent lookups could both resize the table.
    
    The off-heap string table has the following properties:
    
      1) The general hashmap behaviour matches the HashTable, i.e. open
         addressing, power-of-two sized, quadratic probing. This could, of
         course, now be changed.
    
      2) The empty and deleted sentinels are changed to Smi 0 and 1,
         respectively, to make those comparisons a bit cheaper and not
         require roots access.
    
      3) When the HashTable is resized, the old elements array is kept
         alive in a linked list of previous arrays, so that concurrent
         lookups don't lose the data they're accessing. This linked list
         is cleared by the GC, as then we know that all threads are in
         a safepoint.
    
      4) The GC treats the hash table entries as weak roots, and only walks
         them for non-live reference clearing and for evacuation.
    
      5) Since there is no longer a FixedArray to serialize for the startup
         snapshot, there is now a custom serialization of the string table,
         and the string table root is considered unserializable during weak
         root iteration. As a bonus, the custom serialization is more
         efficient, as it skips non-string entries.
    
    As a drive-by, rename LookupStringExists_NoAllocate to
    TryStringToIndexOrLookupExisting, to make it clearer that it returns
    a non-string for the case when the string is an array index. As another
    drive-by, extract StringSet into a separate header.
    
    Bug: v8:10729
    Change-Id: I9c990fb2d74d1fe222920408670974a70e969bca
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2339104
    Commit-Queue: Leszek Swirski <leszeks@chromium.org>
    Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
    Reviewed-by: 's avatarUlan Degenbaev <ulan@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#69270}
    1546be9c
string-set.h 1.46 KB