Skip to content
This repository was archived by the owner on Dec 3, 2022. It is now read-only.
This repository was archived by the owner on Dec 3, 2022. It is now read-only.

decode to object - make lookup faster #82

@milahu

Description

@milahu

what puzzles me is:
why are mappings always decoded into dense arrays
and not into sparse arrays or objects or maps (on demand)?

objects or maps would make 'lookup by column ID' much faster
since the column ID would be used as key

currently we must use some search algorithm (binary search, etc)
to find a segment by its column ID

the only problem i see is the (space and time) overhead of objects / maps
but is it worth .. ?

seems there are two situations:

  1. only a few lookups are done, then dense array + expensive search is faster
  2. many lookups are done, then sparse/object/map + cheap search is faster

= initial cost vs running costs

if you need some code to look at

const mappings_line_dense_array = [
  [0], [2, 0, 0, 2], [4], [8]
];

const mappings_line_sparse_array = [
//0    1  2         3  4    5 6 7  8
  null, , [0, 0, 2], , null, , , , null
];

const mappings_line_object = {
  '0': null, '2': [0, 0, 2], '4': null, '8': null
};

const mappings_line_map = new Map([
  [0, null], [2, [0, 0, 2]], [4, null], [8, null]
]);

edit: or store mappings as new Map() with two-dimensional keys [line, column]

const mappings_map = new Map([
  [[0, 0], null],
  [[0, 2], [0, 0, 2]],
  [[0, 4], null],
  [[0, 8], null]
]);

my intuition says:

  • prefer sparse array, as this is easier to manipulate (insert, concat)
    using sparse array, we delegate optimizations to the javascript implementation
  • object should be slower due to integer-to-string conversion of keys
  • map can only append keys (no random write access, insert/concat is expensive)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @milahu

        Issue actions

          decode to object - make lookup faster · Issue #82 · Rich-Harris/sourcemap-codec