Performance: Buffer Updates - Investigate & benchmark Piece Table approach

[bryphe]

We currently have a sub-optimal strategy for handling buffer updates from Neovim. We do a lot of Array splicing which is slow for large buffers. We should start by benchmarking our existing performance characteristics.

In investigating various data structures that we could use to improve this:

• Rope
• Gap buffer
• Piece Table

The Piece Table is the most appealing to me - it's an immutable data structure, so it's a very natural fit for our language and architecture. We don't necessarily need the undo faculty of it (as we defer that functionality to Neovim) - but we could periodically consolidate the immutable blocks when the application is idle - this would help offset some of the key downsides of the data structure (that it isn't self optimizing, that retrieving a byte involves iterating sequentially over the 'pieces').

[bryphe]

The piece table should drastically reduce the cost of inserting into large buffers, as most of the cost of our previous strategy is because we incur lots of copying / memory cost in creating new arrays when splicing. Ideally, with the piece table strategy, the cost should be the same when inserting in a large buffer or a small buffer.

In the current state of the world, as measured by #96 , that is not the case:

+----------------------------------------------------------------------------------------------------------------------------------------------+
|  BENCHMARK                                      |  TIME               |  MINOR GC  |  MAJOR GC  |  MINOR ALLOC  |  PROMOTED  |  MAJOR ALLOC  |
|-------------------------------------------------+---------------------+------------+------------+---------------+------------+---------------|
|  Buffer: Add lines to empty buffer              |  1.22300958633      |  334       |  67        |  24359        |  1627      |  100002627    |
|-------------------------------------------------+---------------------+------------+------------+---------------+------------+---------------|
|  Buffer: Insert line in middle of small buffer  |  0.000998497009277  |  1         |  0         |  244029       |  25        |  25           |
|-------------------------------------------------+---------------------+------------+------------+---------------+------------+---------------|
|  Buffer: Insert line in middle of large buffer  |  0.546031951904     |  401       |  80        |  42349        |  3945      |  110005945    |
|-------------------------------------------------+---------------------+------------+------------+---------------+------------+---------------|
|  Buffer: Clear large buffer                     |  0.                 |  1         |  0         |  19029        |  25        |  25           |