[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: lynx-dev a BIG optimization for large pages (patch5)
From: |
Leonid Pauzner |
Subject: |
Re: lynx-dev a BIG optimization for large pages (patch5) |
Date: |
Wed, 23 Oct 2002 18:04:57 +0400 (MSD) |
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