Re: lynx-dev a BIG optimization for large pages (patch5)

[Leonid Pauzner]

19-Oct-2002 20:18 you wrote:
> Playing with my large file and a profiler
> I have resolved one more hot point, now in split_line():


> * a *big* optimization for large html files - with thousands of links -
>   remove quadratic complexity from split_line() usage, in GridText.c
>   Because of some work with anchors on the last(=splitted) line,
>   the anchors list was traversed from the beginning for each output line.
>   Now first_anchor is a double-linked list (since reverse search appears),
>   so we can walk from the last_anchor easily.  With my 800Kb test file
>   (13000 output lines, 3100 anchors)  this shows 25% speedup: split_line
>   weight decreased from 26% down to 1%  - LP

Sorry, please ignore this patch #5  (last_anchor->prev was uninitialized:
the list is "double-linked on demand", initialized in www_search_backward),
use this instead:


> diff -u old/gridtext.c ./gridtext.c
> --- old/gridtext.c      Wed Oct 16 02:40:52 2002
> +++ ./gridtext.c        Sat Oct 19 19:17:58 2002
> @@ -3091,7 +3091,6 @@
>       */

>      if (s > 0) {                       /* if not completely empty */
> -       TextAnchor * prev_a = NULL;
>         int moved = 0;

>         /* In the algorithm below we move or not move anchors between
> @@ -3103,7 +3102,14 @@
>          */
>         /* Our operations can make a non-empty all-whitespace link
>            empty.  So what? */
> -       for (a = text->first_anchor; a; prev_a = a, a = a->next) {
> +
> +       /* go up from the last anchor: */
> +       for (a = text->last_anchor; a; a = a->prev) {
> +           if (a->line_num < CurLine)
> +                       break;
> +       }/* and now back: */
> +
> +       for ( ; a; a = a->next) {
>             if (a->line_num == CurLine) {
>                 int len = a->extent, n = a->number, start = a->line_pos;
>                 int end = start + len;



* optimization for large html files - with thousands of links -
  remove quadratic complexity from split_line() usage, in GridText.c
  Because of some work with anchors on the last(=splitted) line,
  the anchors list was traversed from the beginning for each output line.
  Now we store last_anchor_before_split explicitely.  With my 800Kb test
  file (13000 output lines, 3100 anchors)  this shows 25% speedup:
  split_line weight decreased from 26% down to 1%  - LP


diff -u -p old/gridtext.c ./gridtext.c
--- old/gridtext.c      Wed Oct 23 17:38:22 2002
+++ ./gridtext.c        Wed Oct 23 17:25:08 2002
@@ -343,9 +343,10 @@ struct _HText {
 #endif
        HTLine *                last_line;
        int                     Lines;          /* Number of them */
-       TextAnchor *            first_anchor;   /* double-linked list */
+       TextAnchor *            first_anchor;   /* double-linked on demand */
        TextAnchor *            last_anchor;
        TextAnchor *            last_anchor_before_stbl;
+       TextAnchor *            last_anchor_before_split;
        HTList *                forms;          /* also linked internally */
        int                     last_anchor_number;     /* user number */
        BOOL                    source;         /* Is the text source? */
@@ -868,6 +869,7 @@ PUBLIC HText *      HText_new ARGS1(
 #endif
     self->Lines = 0;
     self->first_anchor = self->last_anchor = NULL;
+    self->last_anchor_before_split = NULL;
     self->style = &default_style;
     self->top_of_screen = 0;
     self->node_anchor = anchor;
@@ -2952,9 +2954,9 @@ PRIVATE void split_line ARGS2(
     memcpy(temp, previous, LINE_SIZE(previous->size));
 #if defined(USE_COLOR_STYLE)
     
ALLOC_IN_POOL((text->styles_pool),HTStyleChangePool,previous->numstyles,temp->styles);
-    memcpy(temp->styles, previous->styles, 
sizeof(HTStyleChange)*previous->numstyles);
     if (!temp->styles)
        outofmem(__FILE__, "split_line_2");
+    memcpy(temp->styles, previous->styles, 
sizeof(HTStyleChange)*previous->numstyles);
 #endif
     FREE(previous);
     previous = temp;
@@ -3085,7 +3087,6 @@ PRIVATE void split_line ARGS2(
      */

     if (s > 0) {                       /* if not completely empty */
-       TextAnchor * prev_a = NULL;
        int moved = 0;

        /* In the algorithm below we move or not move anchors between
@@ -3097,10 +3098,16 @@ PRIVATE void split_line ARGS2(
         */
        /* Our operations can make a non-empty all-whitespace link
           empty.  So what? */
-       for (a = text->first_anchor; a; prev_a = a, a = a->next) {
+       a = text->last_anchor_before_split;
+       if (!a)
+           a = text->first_anchor;
+
+       for ( ; a; a = a->next) {
            if (a->line_num == CurLine) {
                int len = a->extent, n = a->number, start = a->line_pos;
                int end = start + len;
+
+               text->last_anchor_before_split = a;

                /* Which anchors do we leave on the previous line?
                   a) empty finished (We need a cut-off value.



; To UNSUBSCRIBE: Send "unsubscribe lynx-dev" to address@hidden