Effective marker handling

[Mike Lischke]

Hi,

in my application I use markers to denote certain lines in my editor content. Since documents can be very large (and many markers can exist, think of a million markers) I try to handle changes as effective as possible. For this I keep a list of markers I have already set and on changes I diff that with what my parser wants to have now to determine which markers should be removed and which added (instead of removing all markers and add new ones, which can result in many useless remove/re-add actions).

This obviously depends heavily on my list being exactly in sync what the editor control has. And this is where my problems occur. In certain circumstances Scintilla modifies markers on its own. Sometimes notifying me (e.g. when a line with a marker is removed) sometimes not (if a new line is inserted before lines with markers). So my list constantly gets out of sync, rendering my entire optimization useless.

This is why I'm looking for better ideas. I was thinking about instead of using my own list I query Scintilla if a line contains a specific marker already. Though this has at least 2 disadvantages:

1) Potentially many roundtrips to Scintilla, making this a slow solution.
2) No solution to remove markers, unless I really iterate over all lines.

Any better idea is welcome,

Mike

[m***@gmail.com]

If I understand you correctly I believe I'm doing something similar to call
an event when a marker position is modified, but it could easily be
modified to keep a list up to date. I'll throw out my solution in case you
or anyone else sees flaws with it that I should address as well. I don't
have 1 million (!!) markers, but for my small set it seems to be working
well although my app is nowhere near ready for real QA or user testing yet.

When SCN_MODIFIED notification is received and only when the
modificationType is SC_MOD_INSERTTEXT or SC_MOD_DELETETEXT I do the
following. APosition and ALinesAdded are pulled directly from
SCNotification.Position and SCNotification.LinesAdded. My DoMarkerUpdate
passes the marker num, the old line it was on, and the new that it is now
on. This approach may still make many trips to Scintilla, but it starts at
the first line of the modified text and asks Scintilla for the next line
containing any markers that are not folding markers (adjust as needed if
you've repurposed folding markers). From the documentation on
SCI_MARKERNEXT... *"**These messages search efficiently for lines that
include a given set of markers."* so my hope is that this is an optimal
approach.

procedure MarkersUpdated(APosition, ALinesAdded: Integer);
var
I, Line, Markers, Mask: Integer;
begin
if ALinesAdded <> 0 then
begin
Line := MarkerNext(LineFromPosition(APosition), $1FFFFFF);

while Line <> -1 do
begin
Markers := MarkerGet(Line);

{ Send notification of any markers that have been updated }
for I := 0 to SC_MARKNUM_FOLDEREND - 1 do
begin
Mask := 1 shl I;
if Markers and Mask = Mask then
DoMarkerUpdate(I, Line - ALinesAdded, Line);
end;

Line := MarkerNext(Line + 1, $1FFFFFF);
end;
end;
end;

Michael

P.S. TVirtualStringTree may quite possibly be my favorite component of all
time. I've been using it for years!

Post by Mike Lischke
Hi,
in my application I use markers to denote certain lines in my editor
content. Since documents can be very large (and many markers can exist,
think of a million markers) I try to handle changes as effective as
possible. For this I keep a list of markers I have already set and on
changes I diff that with what my parser wants to have now to determine
which markers should be removed and which added (instead of removing all
markers and add new ones, which can result in many useless remove/re-add
actions).
This obviously depends heavily on my list being exactly in sync what the
editor control has. And this is where my problems occur. In certain
circumstances Scintilla modifies markers on its own. Sometimes notifying me
(e.g. when a line with a marker is removed) sometimes not (if a new line is
inserted before lines with markers). So my list constantly gets out of
sync, rendering my entire optimization useless.
This is why I'm looking for better ideas. I was thinking about instead of
using my own list I query Scintilla if a line contains a specific marker
1) Potentially many roundtrips to Scintilla, making this a slow solution.
2) No solution to remove markers, unless I really iterate over all lines.
Any better idea is welcome,
Mike
--
www.soft-gems.net

[Mike Lischke]

Hey Michael,

When SCN_MODIFIED notification is received and only when the modificationType is SC_MOD_INSERTTEXT or SC_MOD_DELETETEXT I do the following. APosition and ALinesAdded are pulled directly from SCNotification.Position and SCNotification.LinesAdded. My DoMarkerUpdate passes the marker num, the old line it was on, and the new that it is now on. This approach may still make many trips to Scintilla, but it starts at the first line of the modified text and asks Scintilla for the next line containing any markers that are not folding markers (adjust as needed if you've repurposed folding markers). From the documentation on SCI_MARKERNEXT... "These messages search efficiently for lines that include a given set of markers." so my hope is that this is an optimal approach.

Thanks for your idea! I was focused on using SC_MOD_CHANGEMARKER which doesn't carry much information. Your's looks like a good way to go. I assume you are calling MarkersUpdated directly from your handler for SCN_MODIFIED, right?

procedure MarkersUpdated(APosition, ALinesAdded: Integer);
var
I, Line, Markers, Mask: Integer;
begin
if ALinesAdded <> 0 then
begin
Line := MarkerNext(LineFromPosition(APosition), $1FFFFFF);
while Line <> -1 do
begin
Markers := MarkerGet(Line);
{ Send notification of any markers that have been updated }
for I := 0 to SC_MARKNUM_FOLDEREND - 1 do
begin
Mask := 1 shl I;
if Markers and Mask = Mask then
DoMarkerUpdate(I, Line - ALinesAdded, Line);
end;
Line := MarkerNext(Line + 1, $1FFFFFF);
end;
end;
end;
Michael
P.S. TVirtualStringTree may quite possibly be my favorite component of all time. I've been using it for years!

:-D glad to hear that!

Mike

[m***@gmail.com]

Post by Mike Lischke
I assume you are calling MarkersUpdated directly from your handler for

SCN_MODIFIED, right?

Exactly.

if ASCNotification.ModificationType and (SC_MOD_INSERTTEXT or
SC_MOD_DELETETEXT) <> 0 then
MarkersUpdated(ASCNotification.Position,
ASCNotification.LinesAdded)
else if ASCNotification.ModificationType and SC_MOD_BEFOREDELETE <>
0 then
MarkersDeleted(ASCNotification.Position, ASCNotification.Length);

Michael

Post by Mike Lischke
Hey Michael,
When SCN_MODIFIED notification is received and only when the
modificationType is SC_MOD_INSERTTEXT or SC_MOD_DELETETEXT I do the
following. APosition and ALinesAdded are pulled directly from
SCNotification.Position and SCNotification.LinesAdded. My DoMarkerUpdate
passes the marker num, the old line it was on, and the new that it is now
on. This approach may still make many trips to Scintilla, but it starts at
the first line of the modified text and asks Scintilla for the next line
containing any markers that are not folding markers (adjust as needed if
you've repurposed folding markers). From the documentation on
SCI_MARKERNEXT... *"**These messages search efficiently for lines that
include a given set of markers."* so my hope is that this is an optimal
approach.
Thanks for your idea! I was focused on using SC_MOD_CHANGEMARKER which
doesn't carry much information. Your's looks like a good way to go. I
assume you are calling MarkersUpdated directly from your handler for
SCN_MODIFIED, right?
procedure MarkersUpdated(APosition, ALinesAdded: Integer);
var
I, Line, Markers, Mask: Integer;
begin
if ALinesAdded <> 0 then
begin
Line := MarkerNext(LineFromPosition(APosition), $1FFFFFF);
while Line <> -1 do
begin
Markers := MarkerGet(Line);
{ Send notification of any markers that have been updated }
for I := 0 to SC_MARKNUM_FOLDEREND - 1 do
begin
Mask := 1 shl I;
if Markers and Mask = Mask then
DoMarkerUpdate(I, Line - ALinesAdded, Line);
end;
Line := MarkerNext(Line + 1, $1FFFFFF);
end;
end;
end;
Michael
P.S. TVirtualStringTree may quite possibly be my favorite component of all
time. I've been using it for years!
:-D glad to hear that!
Mike
--
www.soft-gems.net

[m***@gmail.com]

A slight correction to the code for MarkersDeleted posted earlier. The
following should be more accurate. Again, this routine is so that I can
remove a marker from a line when the line is removed. By default Scintilla
is moving the marker to another line. For my application when the line has
been removed the markers are not valid for any other line. I remove the
marker and fire an event to notify my main window of the removal.

procedure MarkersDeleted(APosition, ALength: Integer);
var
Line1, Line2, I, Markers, Mask: Integer;
begin
if ALength > 0 then
begin
Line1 := LineFromPosition(APosition);
Line2 := LineFromPosition(APosition + ALength);

{ Markers are for a line so if the first line in the modification is
being partially
deleted let's start our search on the next line. }
if APosition >= PositionFromLine(Line1) then
Line1 := Line1 + 1;

Line1 := MarkerNext(Line1, $1FFFFFF);
while (Line1 <> -1) and (Line1 <= Line2) do
begin
Markers := MarkerGet(Line1);
MarkerDelete(Line1, -1); // Delete all markers on this line

{ Send notification of any markers that have been removed }
for I := 0 to SC_MARKNUM_FOLDEREND - 1 do
begin
Mask := 1 shl I;

if Markers and Mask = Mask then
DoMarkerDelete(I, Line1);
end;

Line1 := MarkerNext(Line1 + 1, $1FFFFFF);
end;
end;
end;

[m***@gmail.com]

My code doesn't handle marker deletion so perhaps it would need to be used
along with SCN_MODIFIED and SC_MOD_CHANGEMARKER modificationType.

Michael

Post by Mike Lischke
Hi,
in my application I use markers to denote certain lines in my editor
content. Since documents can be very large (and many markers can exist,
think of a million markers) I try to handle changes as effective as
possible. For this I keep a list of markers I have already set and on
changes I diff that with what my parser wants to have now to determine
which markers should be removed and which added (instead of removing all
markers and add new ones, which can result in many useless remove/re-add
actions).
This obviously depends heavily on my list being exactly in sync what the
editor control has. And this is where my problems occur. In certain
circumstances Scintilla modifies markers on its own. Sometimes notifying me
(e.g. when a line with a marker is removed) sometimes not (if a new line is
inserted before lines with markers). So my list constantly gets out of
sync, rendering my entire optimization useless.
This is why I'm looking for better ideas. I was thinking about instead of
using my own list I query Scintilla if a line contains a specific marker
1) Potentially many roundtrips to Scintilla, making this a slow solution.
2) No solution to remove markers, unless I really iterate over all lines.
Any better idea is welcome,
Mike
--
www.soft-gems.net

[m***@gmail.com]

Correction to my previous comment. I do handle marker removal, but mainly
because I wanted to override the default behavior where markers for a line
are not deleted with the line is removed. For that I'm reacting to the
SC_MOD_BEFOREDELETE modificationType of SCN_MODIFIED and calling the
following. SCNotification.Position and SCNotification.Length are the params
passed.

procedure MarkersDeleted(APosition, ALength: Integer);
var
Line1, Line2, I, Markers, Mask: Integer;
begin
if ALength > 0 then
begin
Line1 := LineFromPosition(APosition);
Line2 := LineFromPosition(APosition + ALength - 1);

{ Markers are for a line so if the first line in the modification is
being partially
deleted let's start our search on the next line. }
if APosition > PositionFromLine(Line1) then
Line1 := Line1 + 1;

Line1 := MarkerNext(Line1, $1FFFFFF);
while (Line1 <> -1) and (Line1 <= Line2) do
begin
Markers := MarkerGet(Line1);
MarkerDelete(Line1, -1); // Delete all markers on this line

{ Send notification of any markers that have been removed }
for I := 0 to SC_MARKNUM_FOLDEREND - 1 do
begin
Mask := 1 shl I;

if Markers and Mask = Mask then
DoMarkerDelete(I, Line1);
end;

Line1 := MarkerNext(Line1 + 1, $1FFFFFF);
end;
end;
end;

Post by Mike Lischke
Hi,
in my application I use markers to denote certain lines in my editor
content. Since documents can be very large (and many markers can exist,
think of a million markers) I try to handle changes as effective as
possible. For this I keep a list of markers I have already set and on
changes I diff that with what my parser wants to have now to determine
which markers should be removed and which added (instead of removing all
markers and add new ones, which can result in many useless remove/re-add
actions).
This obviously depends heavily on my list being exactly in sync what the
editor control has. And this is where my problems occur. In certain
circumstances Scintilla modifies markers on its own. Sometimes notifying me
(e.g. when a line with a marker is removed) sometimes not (if a new line is
inserted before lines with markers). So my list constantly gets out of
sync, rendering my entire optimization useless.
This is why I'm looking for better ideas. I was thinking about instead of
using my own list I query Scintilla if a line contains a specific marker
1) Potentially many roundtrips to Scintilla, making this a slow solution.
2) No solution to remove markers, unless I really iterate over all lines.
Any better idea is welcome,
Mike
--
www.soft-gems.net

[Neil Hodgson]

Post by Mike Lischke
in my application I use markers to denote certain lines in my editor content. Since documents can be very large (and many markers can exist, think of a million markers) I try to handle changes as effective as possible.

Markers were designed to be used for break-points, current line arrows and bookmarks with fairly low numbers. They may not scale well to a million instances.

For very large numbers of markers, optimising may depend on the applications particular patterns of operations. It will depend on how information is split between the application and Scintilla. Michael Staszewski's approach may work well when Scintilla can remain the main source of data.

In other circumstances, particularly when there is more application data associated with each line, it may be preferable to move responsibility to the application. Here, the application will need to respond to insertion and deletion of lines by adding or removing items from its data structures. In this mode, Scintilla's markers become a dumb visual representation of the application data structures. Then the application will be responsible for updating Scintilla to match the single source of truth.

Performance on large documents can often be improved by background incremental updates. The only markers that really need to be set in Scintilla are for the set of lines the user can see, although setting marks for lines above and below may avoid revealing incorrect information temporarily when scrolling. For 3.4.2, SciTE has moved to background (idle time) match marking which can include markers for the Match All command. It divides the file first into three blocks, lines around the visible area (40 before, 40 after), then those after and those before. It synchronously marks matches in the first block (including all the visible lines). Then, as an idle task, it breaks off sub-blocks of up to 200 lines and marks those, eventually terminating.
http://sourceforge.net/p/scintilla/scite/ci/default/tree/src/MatchMarker.cxx

There are various improvements that could be made to this: perhaps ping-ponging between lines after and lines before. Another approach would only mark the range around the visible area and leave the rest of the file in an arbitrary state.

Neil

[Mike Lischke]

Hey Neil,

Post by Neil Hodgson
Markers were designed to be used for break-points, current line arrows and bookmarks with fairly low numbers. They may not scale well to a million instances.

That's how I use them, but in addition to that I mark each valid statement in the file with a marker too, which can lead to a large number of markers. Additionally, I prefer implementing features that work fairly well for heavy load, ensuring so they are really fast in everyday scenarios.

Post by Neil Hodgson
For very large numbers of markers, optimising may depend on the applications particular patterns of operations. It will depend on how information is split between the application and Scintilla. Michael Staszewski's approach may work well when Scintilla can remain the main source of data.

Yes, I think Michael's approach may fit perfectly. I have no separate data stored (except for the marker lines).

Post by Neil Hodgson
Performance on large documents can often be improved by background incremental updates. The only markers that really need to be set in Scintilla are for the set of lines the user can see, although setting marks for lines above and below may avoid revealing incorrect information temporarily when scrolling. For 3.4.2, SciTE has moved to background (idle time) match marking which can include markers for the Match All command. It divides the file first into three blocks, lines around the visible area (40 before, 40 after), then those after and those before. It synchronously marks matches in the first block (including all the visible lines). Then, as an idle task, it breaks off sub-blocks of up to 200 lines and marks those, eventually terminating.
http://sourceforge.net/p/scintilla/scite/ci/default/tree/src/MatchMarker.cxx

That probably needs to be adjusted to re-create the clusters again if the user moves quickly within the file (e.g. jump to end). Then you need to update those lines immediately before continuing with the background work.

Mike