#1733 [PATCH] Use std::list as a base of MarkerHandleSet

Bug
closed-fixed
5
2015-06-20
2015-06-08
Jiri Techet
No

When using git-changebar plugin under Geany (which displays vertical line indicating changed lines), removing many lines, e.g. using undo, causes long delays. After profiling, I found this is because MarkerHandleSet::CombineWith() has to walk the
whole list every time a single line is removed (see the attached svg with the profile and the commit message for more information).

While the git-changebar plugin could probably be modified to remove the markers before the undo action (and not after it which is the case now), it's probably better to fix this in Scintilla because the issue is not obvious from the outside.

This patch uses std::list which contains pointers both to the beginning and the end of the list so no traversing is needed. It would be possible to use std::set too but since the set would have to be defined on (handle, number) and most of the operations look for either handle or number, we would have to walk the set linearly anyway (and walking the RB tree of set might be slower).

1 Attachments

Discussion

  • Jiri Techet

    Jiri Techet - 2015-06-08

    Here's the profile.

     
  • Neil Hodgson

    Neil Hodgson - 2015-06-08

    A single line may contain thousands of elements? That sounds like a new marker is being added for each edition of a line which is a quite heavy use of memory.

     
  • Jiri Techet

    Jiri Techet - 2015-06-09

    No. Initially there is one per line but because of the

    "Retain the markers from the deleted line by oring them into the previous line"

    feature of LineMarkers::RemoveLine(), they are getting accumulated into a single line. If you have 4 lines each with a marker and they get removed one by one - which apparently happens in undo - the marker number after first removal looks like

    1
    1
    2

    after second

    1
    3

    after third

    4

    For 1000 lines removed you get 1000 markers in the list.

     
  • Neil Hodgson

    Neil Hodgson - 2015-06-09

    This is replacing a singly linked list with a doubly linked list so adds a pointer to each marker instance. The std::list container implementation commonly contains 2 pointer-sized members for C++98 and 3 for C++11 (extra member to hold number of elements to ensure size() is constant time) whereas MarkerHandleSet contains a single pointer.

    I'm not saying these increases are necessarily a stopper but there is a storage cost to this change.

    Wouldn't the deletion slowdown be fixed by adding and maintaining a 'last' pointer in MarkerHandleSet? This would increase the size of MarkerHandleSet but it would still be less than or equal to std::list and would avoid adding a pointer to each marker instance.

     
  • Jiri Techet

    Jiri Techet - 2015-06-09

    OK, even though it's a bit of space-overoptimizing IMO (I don't think the difference would matter if you consider the size taken by the rest), I think I might have even better solution than keeping the pointer to the last element.

    First, in the previous comment I wrote the numbers of markers per line in a wrong way, it's actually the other way round

    2
    1
    1

    3
    1

    4

    The lines are removed from the beginning to the end. This means we can just swap the order the lists are joined in MarkerHandleSet::CombineWith() so we don't walk the current line with many markers and instead walk the next line with a single marker, append the current line markers to it and set it as a root (in other words, prepend next line's markers to the current line's).

    See the attached patch. This fixes the problem for me.

    Question: This will clearly work only when lines are removed from the start to the end and not in the opposite direction. Is it always the case in Scintilla when doing bulk operations (undo, removing large selections)?

     
    • Neil Hodgson

      Neil Hodgson - 2015-06-09

      Changes that improve the space or time performance for one user should not cost other users without need.

      Multi-line deletions are performed in the order of increasing line numbers.

       
  • Jiri Techet

    Jiri Techet - 2015-06-10

    Good, then I think the patch which just swaps the order of appending could be used, what do you think? (and it's completely free space-wise)

     
    • Neil Hodgson

      Neil Hodgson - 2015-06-10

      Its still leaving long lists attached to the line. When markers were implemented there were several use cases and some, such as break points, required being able to track back from the line to application data. Therefore handles are allocated and preserved. Your application appears uninterested in this tracking so would be better served by anonymous markers where the CombineWith operation only produces a single element for each marker number possibly with a 'use count' that is increased.

       
  • Jiri Techet

    Jiri Techet - 2015-06-10

    Yes, but all the extra markers are removed immediately afterwards so it isn't a problem in practice.

    I'm a bit confused regarding the "anonymous markers" - is it something that exists in Scintilla or something which would be nice to have in Scintilla? If it exists, could you point me to the documentation how to create/use them?

     
    • Neil Hodgson

      Neil Hodgson - 2015-06-11

      Anonymous markers are not currently implemented in Scintilla. The original implementation of markers did not have handles and markers were stored as a 32-bit bit set per line. There was an intention when handles were added that handles would only be used when needed but that isn't in the current code.

       
  • Jiri Techet

    Jiri Techet - 2015-06-11

    In that case I think the (second) patch I provided is a reasonable (and really simple) solution for the time being, what do you think?

     
    • Neil Hodgson

      Neil Hodgson - 2015-06-11

      Its probably OK but I may think about it some more.

       
  • Jiri Techet

    Jiri Techet - 2015-06-11

    Good, thanks.

     
  • Neil Hodgson

    Neil Hodgson - 2015-06-12
    • labels: --> scintilla, markers, performance
    • status: open --> open-fixed
    • assigned_to: Neil Hodgson
     
  • Neil Hodgson

    Neil Hodgson - 2015-06-20
    • status: open-fixed --> closed-fixed
     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks