> *If* we can do so without turning the CList-construction behavior from
> linear to quadratic (which I suspect we can do, with our patched version
> of a GtkCList), I think we could, alternatively, use
> "gtk_clist_set_row_data()" to associate with each row in the CList a
> pointer to the "frame_data" structure for the row, and have
> "select_packet()" use that to find the row, rather than scanning the
> list of frames for the frame with the specified row number.
>
> (I think we did that once upon a time, and I got rid of it because it
> made the CList-construction quadratic, which meant that reading in a
> Really Big Capture File wasn't just slow, it was *really really* slow;
> later, some other stuff wasn't quite so easy to eliminate, so I fixed
> the GtkCList code so that doing stuff to the *last* row could be done in
> constant time rather than in a time proportional to the size of the
> list, which I think makes doing a "gtk_clist_set_row_data()" right after
> adding an entry to the list no longer make list-construction quadratic
> in the ultimate size of the list.)
Yup. It does - it didn't take any more time to read in one Really Big
Capture File I have.
(Most of the time is spent in "strncpy()", and most of the calls to it
come from...
..."col_add_str()" and "col_set_addr()", setting multiple columns for
over 100,000 rows, most of which will never see the light of day^H^H^Hmy
monitor.
See my comments about a "lazy" GtkCList in the message to which this is
a reply.)
I just checked in a change to do use "gtk_clist_set_row_data()" to
associate a pointer to the "frame_data" structure for a frame with the
row in which the frame appears, and to get rid of the "row" field in the
"frame_data" structure, and it appears to make the patch to add
sortability on arbitrary columns work, in that clicking on a given frame
causes the correct data to show up in the protocol tree window.
(The checkin comment was:
We already set the foreground and background color for every frame,
which means we're already doing a "do something to the last row in the
packet list" operation on every frame we add to the list, so adding a
call to "gtk_clist_set_row_data()" won't make matters worse.
In addition, we already set one column in a row on a "change time
format" operation, so finding the row for a frame by calling
"gtk_clist_find_row_from_data()" doesn't turn a constant-time operation
into a linear-time operation, it just cranks the proportionality
constant up - it was quadratic before, alas, and it's still quadratic.
Adding calls to "gtk_clist_find_row_from_data()" to the "Find Frame" and
"Go To Frame" code does add an extra linear operation there, but those
operations shouldn't be common - and "Go To Frame", going to the last
frame on an ~100,000-frame big capture file, was quick, at least on my
450 MHz Pentium II machine, so maybe it won't be too bad.
And "select_packet()" either has to search the frame table for the frame
with the specified row number, or has to call "gtk_clist_get_row_data()"
to do that - the first is linear in the position of the frame in the
frame table, and the latter is linear in its position in the CList, and
the latter is less than or equal to the former, so the only thing making
it worse would be a change in the proportionality constant.
So it probably won't hurt performance by much.
Furthermore, if we add the ability to sort the display on an arbitrary
column, or to delete frames from the display - both of which are in the
wish list - storing the row number of the frame in the "frame_data"
structure won't necessarily work, as the row number can change out from
under us.
Therefore, reinstate the old way of doing things, where we associate
with each row a pointer to the "frame_data" structure for the row, using
"gtk_clist_set_row_data()".
which discusses the performance issues I could see.
As per the discussion of the "lazy" CList in the mail to which this is a
response, "change time format" can probably be made *very* fast with a
"lazy" CList. We can perhaps speed up some of the other stuff above as
well if we do our own CList replacement.)