Improving resizehistents()

Improving resizehistents()

[Wayne Davison]

While I was looking at the HISTSIZE stuff, I noticed that the
resizehistents() function does not respect the HIST_EXPIRE_DUPS_FIRST
option.  I decided to break out the code that deals with this into a
separate function that could be used by both prepnexthistent() and
resizehistents().  Here's the result.

Optimization note: when the new putoldhistentryontop() function is
called in a loop with the HIST_EXPIRE_DUPS_FIRST option set, it is
possible that we could scan the start of the history list once for
every line we remove.  While I could complicate the function and
make it possible for the scan to continue where it left off, I
decided to leave it simple (and inefficient).  I think this is the
right choice since resizehistents() doesn't get called a lot.  If
anyone disagrees, let me know.

..wayne..

---8<------8<------8<------8<---cut here--->8------>8------>8------>8---
Index: Src/hist.c
--- Src/hist.c	6 Feb 2002 16:48:28 -0000	1.37
+++ Src/hist.c	12 Feb 2002 22:55:46 -0000
@@ -913,11 +913,34 @@
     return he;
 }

+static void
+putoldhistentryontop(void)
+{
+    Histent he = hist_ring->down;
+    if (isset(HISTEXPIREDUPSFIRST) && !(he->flags & HIST_DUP)) {
+	int max_unique_ct = getiparam("SAVEHIST");
+	do {
+	    if (max_unique_ct-- <= 0) {
+		he = hist_ring->down;
+		break;
+	    }
+	    he = he->down;
+	} while (he != hist_ring->down && !(he->flags & HIST_DUP));
+	if (he != hist_ring->down) {
+	    he->up->down = he->down;
+	    he->down->up = he->up;
+	    he->up = hist_ring;
+	    he->down = hist_ring->down;
+	    hist_ring->down = he->down->up = he;
+	}
+    }
+    hist_ring = he;
+}
+
 /**/
 Histent
 prepnexthistent(void)
 {
-    Histent he;
     int curline_in_ring = hist_ring == &curline;

     if (curline_in_ring)
@@ -928,7 +951,7 @@
     }

     if (histlinect < histsiz) {
-	he = (Histent)zcalloc(sizeof *he);
+	Histent he = (Histent)zcalloc(sizeof *he);
 	if (!hist_ring)
 	    hist_ring = he->up = he->down = he;
 	else {
@@ -940,30 +963,13 @@
 	histlinect++;
     }
     else {
-	he = hist_ring->down;
-	if (isset(HISTEXPIREDUPSFIRST) && !(he->flags & HIST_DUP)) {
-	    int max_unique_ct = getiparam("SAVEHIST");
-	    do {
-		if (max_unique_ct-- <= 0) {
-		    he = hist_ring->down;
-		    break;
-		}
-		he = he->down;
-	    } while (he != hist_ring->down && !(he->flags & HIST_DUP));
-	    if (he != hist_ring->down) {
-		he->up->down = he->down;
-		he->down->up = he->up;
-		he->up = hist_ring;
-		he->down = hist_ring->down;
-		hist_ring->down = he->down->up = he;
-	    }
-	}
-	freehistdata(hist_ring = he, 0);
+	putoldhistentryontop();
+	freehistdata(hist_ring, 0);
     }
-    he->histnum = ++curhist;
+    hist_ring->histnum = ++curhist;
     if (curline_in_ring)
 	linkcurline();
-    return he;
+    return hist_ring;
 }

 /* A helper function for hend() */
@@ -1756,8 +1762,10 @@
 void
 resizehistents(void)
 {
-    while (histlinect > histsiz)
-	freehistnode((HashNode)hist_ring->down);
+    while (histlinect > histsiz) {
+	putoldhistentryontop();
+	freehistnode((HashNode)hist_ring);
+    }
 }

 /* Remember the last line in the history file so we can find it again. */
---8<------8<------8<------8<---cut here--->8------>8------>8------>8---

Re: Improving resizehistents()

[Bart Schaefer]

On Feb 12,  6:00pm, Wayne Davison wrote:
}
[...]
} possible that we could scan the start of the history list once for
} every line we remove.  While I could complicate the function and
} make it possible for the scan to continue where it left off, I
} decided to leave it simple (and inefficient).

My intuition is that you've made the right choice, but I know there are
some people out there using HISTSIZE into the many thousands.  How big
can the history get before this creates a noticeable delay?

-- 
Bart Schaefer                                 Brass Lantern Enterprises
http://www.well.com/user/barts              http://www.brasslantern.com

Zsh: http://www.zsh.org | PHPerl Project: http://phperl.sourceforge.net   

Re: Improving resizehistents()

[Wayne Davison]

On Wed, 13 Feb 2002, Bart Schaefer wrote:
> My intuition is that you've made the right choice, but I know there are
> some people out there using HISTSIZE into the many thousands.  How big
> can the history get before this creates a noticeable delay?

I tried the following test with $n set to 10000, 20000, and 100000:

    setopt histexpiredupsfirst
    HISTSIZE=$n
    SAVEHIST=$n
    fc -R unique$n
    date ; HISTSIZE=1 ; date

(Of course, the file unique10000 had 10000 unique commands in it, etc.)

The results for the current code on my PII 433 are:

 10000:  4 secs
 20000: 31 secs
100000: [killed zsh after over 7 minutes of 98% cpu usage]

I then tested a function that I wrote that allows restarting the scan:

 10000: 0 secs
 20000: 0 secs
100000: 0 secs

I've appended a diff between my first patch and the new code.  It's a
bit more complex, but not too bad.  I think I'll commit it after a
little more testing.  Feel free to let me know what you think.

..wayne..

---8<------8<------8<------8<---cut here--->8------>8------>8------>8---
Index: Src/hist.c
--- Src/hist.c	13 Feb 2002 18:13:14 -0000	1.38
+++ Src/hist.c	13 Feb 2002 18:27:48 -0000
@@ -914,17 +914,23 @@
 }

 static void
-putoldhistentryontop(void)
+putoldhistentryontop(short keep_going)
 {
-    Histent he = hist_ring->down;
+    static Histent next = NULL;
+    Histent he = keep_going? next : hist_ring->down;
     if (isset(HISTEXPIREDUPSFIRST) && !(he->flags & HIST_DUP)) {
-	int max_unique_ct = getiparam("SAVEHIST");
+	static int max_unique_ct = 0;
+	if (!keep_going)
+	    max_unique_ct = getiparam("SAVEHIST");
+	next = he->down;
 	do {
 	    if (max_unique_ct-- <= 0) {
+		max_unique_ct = 1; /* On next keep_going, scan 1 more entry */
 		he = hist_ring->down;
 		break;
 	    }
-	    he = he->down;
+	    he = next;
+	    next = he->down;
 	} while (he != hist_ring->down && !(he->flags & HIST_DUP));
 	if (he != hist_ring->down) {
 	    he->up->down = he->down;
@@ -963,7 +969,7 @@
 	histlinect++;
     }
     else {
-	putoldhistentryontop();
+	putoldhistentryontop(0);
 	freehistdata(hist_ring, 0);
     }
     hist_ring->histnum = ++curhist;
@@ -1762,9 +1768,13 @@
 void
 resizehistents(void)
 {
-    while (histlinect > histsiz) {
-	putoldhistentryontop();
+    if (histlinect > histsiz) {
+	putoldhistentryontop(0);
 	freehistnode((HashNode)hist_ring);
+	while (histlinect > histsiz) {
+	    putoldhistentryontop(1);
+	    freehistnode((HashNode)hist_ring);
+	}
     }
 }

---8<------8<------8<------8<---cut here--->8------>8------>8------>8---

Re: Improving resizehistents()

[Wayne Davison]

On Wed, 13 Feb 2002, Wayne Davison wrote:
> I've appended a diff between my first patch and the new code.

Yeesh.  That function was totally wacked except when there were no dups.
This version appears to work both correctly and quickly.

..wayne..

---8<------8<------8<------8<---cut here--->8------>8------>8------>8---
Index: Src/hist.c
--- Src/hist.c	13 Feb 2002 18:13:14 -0000	1.38
+++ Src/hist.c	13 Feb 2002 19:21:26 -0000
@@ -914,25 +914,31 @@
 }

 static void
-putoldhistentryontop(void)
+putoldhistentryontop(short keep_going)
 {
-    Histent he = hist_ring->down;
+    static Histent next = NULL;
+    Histent he = keep_going? next : hist_ring->down;
+    next = he->down;
     if (isset(HISTEXPIREDUPSFIRST) && !(he->flags & HIST_DUP)) {
-	int max_unique_ct = getiparam("SAVEHIST");
+	static int max_unique_ct = 0;
+	if (!keep_going)
+	    max_unique_ct = getiparam("SAVEHIST");
 	do {
 	    if (max_unique_ct-- <= 0) {
+		max_unique_ct = 0;
 		he = hist_ring->down;
 		break;
 	    }
-	    he = he->down;
+	    he = next;
+	    next = he->down;
 	} while (he != hist_ring->down && !(he->flags & HIST_DUP));
-	if (he != hist_ring->down) {
-	    he->up->down = he->down;
-	    he->down->up = he->up;
-	    he->up = hist_ring;
-	    he->down = hist_ring->down;
-	    hist_ring->down = he->down->up = he;
-	}
+    }
+    if (he != hist_ring->down) {
+	he->up->down = he->down;
+	he->down->up = he->up;
+	he->up = hist_ring;
+	he->down = hist_ring->down;
+	hist_ring->down = he->down->up = he;
     }
     hist_ring = he;
 }
@@ -963,7 +969,7 @@
 	histlinect++;
     }
     else {
-	putoldhistentryontop();
+	putoldhistentryontop(0);
 	freehistdata(hist_ring, 0);
     }
     hist_ring->histnum = ++curhist;
@@ -1762,9 +1768,13 @@
 void
 resizehistents(void)
 {
-    while (histlinect > histsiz) {
-	putoldhistentryontop();
+    if (histlinect > histsiz) {
+	putoldhistentryontop(0);
 	freehistnode((HashNode)hist_ring);
+	while (histlinect > histsiz) {
+	    putoldhistentryontop(1);
+	    freehistnode((HashNode)hist_ring);
+	}
     }
 }

---8<------8<------8<------8<---cut here--->8------>8------>8------>8---