Re: [Monotone-devel] Netsync performance improvement patch

[Eric Anderson]

Matt Johnston writes:
 > I assume that a boost::circular_buffer isn't suitable since
 > that doesn't have contiguous storage?

Since the question about contigous storage came up again, I took a
closer look at the circular_buffer. Last time I just looked at it, saw
it had non-contigous storage, and figured it would require much
re-work to get it to do the right thing.

In my second review, I learned that:

  1) circular_buffer has a linearize() function that forces the data into
     contigous order.  I missed this in the last examination.
  2) linearize() as currently implemented would be very slow for
     characters (it copies each character one by one).
  3) extracting strings out of a circular_buffer would be very slow as 
     it would either be a call to linearize() or a character by character
     extraction as there is no access to the underlying array it uses to
     store the data.
  4) inserting strings would have the same problem as extracting except 
     that the only way to do the insertion would be character by 
     character.
  5) the circular_buffer doesn't auto-resize when full, it overwrites the
     head of the buffer (I read through way too fast last time, and made
     assumptions based on the name).  This is not a show-stopper, but is
     very inconvinient for usage in monotone as it requires the wrapper 
     code to always check that enough space exists in the buffer and 
     resize if it doesn't.

So the conclusion of not being able to use a circular_buffer still stands, 
but not because of the lack of contigous storage, but because of the
lack of being able to efficiently insert/remove contigous data.
        -Eric