Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys Optimization suggested by Bill Sommerfeld: Keep a hint ...
details: https://anonhg.NetBSD.org/src/rev/2a0b941b06a9
branches: trunk
changeset: 514835:2a0b941b06a9
user: thorpej <thorpej%NetBSD.org@localhost>
date: Tue Sep 11 04:32:19 2001 +0000
description:
Optimization suggested by Bill Sommerfeld: Keep a hint as to the
"earliest" firing callout in a bucket. This allows us to skip
the scan up the bucket if no callouts are due in the bucket.
A cheap O(1) hint update is done at callout insertion (if new callout
is earlier than hint) and removal (is bucket empty). A thorough
refresh of the hint is done when the bucket is traversed.
This doesn't matter much on machines with small values of hz
(e.g. i386), but on systems with large values of hz (e.g. Alpha),
it has a definite positive effect.
Also, keep the callwheel stats in evcnts, so that you can view them
with "vmstat -e".
diffstat:
sys/ddb/db_xxx.c | 30 ++++++---
sys/kern/kern_clock.c | 148 +++++++++++++++++++++++++++++++++++--------------
sys/sys/callout.h | 7 +-
3 files changed, 129 insertions(+), 56 deletions(-)
diffs (truncated from 332 to 300 lines):
diff -r a87815a70272 -r 2a0b941b06a9 sys/ddb/db_xxx.c
--- a/sys/ddb/db_xxx.c Tue Sep 11 04:10:41 2001 +0000
+++ b/sys/ddb/db_xxx.c Tue Sep 11 04:32:19 2001 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: db_xxx.c,v 1.12 2001/07/31 04:28:16 atatat Exp $ */
+/* $NetBSD: db_xxx.c,v 1.13 2001/09/11 04:32:19 thorpej Exp $ */
/*
* Copyright (c) 1982, 1986, 1989, 1991, 1993
@@ -201,20 +201,30 @@
{
extern struct callout_queue *callwheel;
extern int callwheelsize;
+ uint64_t hint;
int i;
for (i = 0; i < callwheelsize; i++) {
struct callout_queue *bucket = &callwheel[i];
- struct callout *c = TAILQ_FIRST(bucket);
+ struct callout *c = TAILQ_FIRST(&bucket->cq_q);
- if (c) db_printf("bucket %d:\n", i);
- while (c) {
- db_printf("%p: time %llx arg %p flags %x func %p: ",
- c, (long long) c->c_time, c->c_arg,
- c->c_flags, c->c_func);
- db_printsym((u_long)c->c_func, DB_STGY_PROC, db_printf);
- db_printf("\n");
- c = TAILQ_NEXT(c, c_link);
+ if (c) {
+ db_printf("bucket %d (hint %llx):\n", i,
+ (long long) bucket->cq_hint);
+ hint = UQUAD_MAX;
+ while (c) {
+ if (c->c_time < hint)
+ hint = c->c_time;
+ db_printf("%p: time %llx arg %p flags %x "
+ "func %p: ", c, (long long) c->c_time,
+ c->c_arg, c->c_flags, c->c_func);
+ db_printsym((u_long)c->c_func, DB_STGY_PROC,
+ db_printf);
+ db_printf("\n");
+ c = TAILQ_NEXT(c, c_link);
+ }
+ if (bucket->cq_hint < hint)
+ printf("** HINT IS STALE\n");
}
}
}
diff -r a87815a70272 -r 2a0b941b06a9 sys/kern/kern_clock.c
--- a/sys/kern/kern_clock.c Tue Sep 11 04:10:41 2001 +0000
+++ b/sys/kern/kern_clock.c Tue Sep 11 04:32:19 2001 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_clock.c,v 1.75 2001/05/06 13:46:34 simonb Exp $ */
+/* $NetBSD: kern_clock.c,v 1.76 2001/09/11 04:32:20 thorpej Exp $ */
/*-
* Copyright (c) 2000 The NetBSD Foundation, Inc.
@@ -91,6 +91,9 @@
#include <sys/sysctl.h>
#include <sys/timex.h>
#include <sys/sched.h>
+#ifdef CALLWHEEL_STATS
+#include <sys/device.h>
+#endif
#include <machine/cpu.h>
#ifdef __HAVE_GENERIC_SOFT_INTERRUPTS
@@ -354,17 +357,18 @@
static struct callout *nextsoftcheck; /* next callout to be checked */
#ifdef CALLWHEEL_STATS
-int callwheel_collisions; /* number of hash collisions */
-int callwheel_maxlength; /* length of the longest hash chain */
-int *callwheel_sizes; /* per-bucket length count */
-u_int64_t callwheel_count; /* # callouts currently */
-u_int64_t callwheel_established; /* # callouts established */
-u_int64_t callwheel_fired; /* # callouts that fired */
-u_int64_t callwheel_disestablished; /* # callouts disestablished */
-u_int64_t callwheel_changed; /* # callouts changed */
-u_int64_t callwheel_softclocks; /* # times softclock() called */
-u_int64_t callwheel_softchecks; /* # checks per softclock() */
-u_int64_t callwheel_softempty; /* # empty buckets seen */
+int *callwheel_sizes; /* per-bucket length count */
+struct evcnt callwheel_collisions; /* number of hash collisions */
+struct evcnt callwheel_maxlength; /* length of the longest hash chain */
+struct evcnt callwheel_count; /* # callouts currently */
+struct evcnt callwheel_established; /* # callouts established */
+struct evcnt callwheel_fired; /* # callouts that fired */
+struct evcnt callwheel_disestablished; /* # callouts disestablished */
+struct evcnt callwheel_changed; /* # callouts changed */
+struct evcnt callwheel_softclocks; /* # times softclock() called */
+struct evcnt callwheel_softchecks; /* # checks per softclock() */
+struct evcnt callwheel_softempty; /* # empty buckets seen */
+struct evcnt callwheel_hintworked; /* # times hint saved scan */
#endif /* CALLWHEEL_STATS */
/*
@@ -881,7 +885,7 @@
*/
simple_lock(&callwheel_slock); /* already at splclock() */
hardclock_ticks++;
- if (TAILQ_FIRST(&callwheel[hardclock_ticks & callwheelmask]) != NULL) {
+ if (! TAILQ_EMPTY(&callwheel[hardclock_ticks & callwheelmask].cq_q)) {
simple_unlock(&callwheel_slock);
if (CLKF_BASEPRI(frame)) {
/*
@@ -931,23 +935,34 @@
softclock_running = 1;
#ifdef CALLWHEEL_STATS
- callwheel_softclocks++;
+ callwheel_softclocks.ev_count++;
#endif
while (softclock_ticks != hardclock_ticks) {
softclock_ticks++;
idx = (int)(softclock_ticks & callwheelmask);
bucket = &callwheel[idx];
- c = TAILQ_FIRST(bucket);
+ c = TAILQ_FIRST(&bucket->cq_q);
+ if (c == NULL) {
#ifdef CALLWHEEL_STATS
- if (c == NULL)
- callwheel_softempty++;
+ callwheel_softempty.ev_count++;
#endif
+ continue;
+ }
+ if (softclock_ticks < bucket->cq_hint) {
+#ifdef CALLWHEEL_STATS
+ callwheel_hintworked.ev_count++;
+#endif
+ continue;
+ }
+ bucket->cq_hint = UQUAD_MAX;
while (c != NULL) {
#ifdef CALLWHEEL_STATS
- callwheel_softchecks++;
+ callwheel_softchecks.ev_count++;
#endif
if (c->c_time != softclock_ticks) {
+ if (c->c_time < bucket->cq_hint)
+ bucket->cq_hint = c->c_time;
c = TAILQ_NEXT(c, c_link);
if (++steps >= MAX_SOFTCLOCK_STEPS) {
nextsoftcheck = c;
@@ -959,11 +974,11 @@
}
} else {
nextsoftcheck = TAILQ_NEXT(c, c_link);
- TAILQ_REMOVE(bucket, c, c_link);
+ TAILQ_REMOVE(&bucket->cq_q, c, c_link);
#ifdef CALLWHEEL_STATS
callwheel_sizes[idx]--;
- callwheel_fired++;
- callwheel_count--;
+ callwheel_fired.ev_count++;
+ callwheel_count.ev_count--;
#endif
func = c->c_func;
arg = c->c_arg;
@@ -976,6 +991,8 @@
c = nextsoftcheck;
}
}
+ if (TAILQ_EMPTY(&bucket->cq_q))
+ bucket->cq_hint = UQUAD_MAX;
}
nextsoftcheck = NULL;
softclock_running = 0;
@@ -1007,10 +1024,35 @@
{
int i;
- for (i = 0; i < callwheelsize; i++)
- TAILQ_INIT(&callwheel[i]);
+ for (i = 0; i < callwheelsize; i++) {
+ callwheel[i].cq_hint = UQUAD_MAX;
+ TAILQ_INIT(&callwheel[i].cq_q);
+ }
simple_lock_init(&callwheel_slock);
+
+#ifdef CALLWHEEL_STATS
+ evcnt_attach_dynamic(&callwheel_collisions, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "collisions");
+ evcnt_attach_dynamic(&callwheel_maxlength, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "maxlength");
+ evcnt_attach_dynamic(&callwheel_count, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "count");
+ evcnt_attach_dynamic(&callwheel_established, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "established");
+ evcnt_attach_dynamic(&callwheel_fired, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "fired");
+ evcnt_attach_dynamic(&callwheel_disestablished, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "disestablished");
+ evcnt_attach_dynamic(&callwheel_changed, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "changed");
+ evcnt_attach_dynamic(&callwheel_softclocks, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "softclocks");
+ evcnt_attach_dynamic(&callwheel_softempty, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "softempty");
+ evcnt_attach_dynamic(&callwheel_hintworked, EVCNT_TYPE_MISC,
+ NULL, "callwheel", "hintworked");
+#endif /* CALLWHEEL_STATS */
}
/*
@@ -1049,7 +1091,7 @@
if (c->c_flags & CALLOUT_PENDING) {
callout_stop_locked(c); /* Already locked */
#ifdef CALLWHEEL_STATS
- callwheel_changed++;
+ callwheel_changed.ev_count++;
#endif
}
@@ -1061,17 +1103,20 @@
bucket = &callwheel[c->c_time & callwheelmask];
#ifdef CALLWHEEL_STATS
- if (TAILQ_FIRST(bucket) != NULL)
- callwheel_collisions++;
+ if (! TAILQ_EMPTY(&bucket->cq_q))
+ callwheel_collisions.ev_count++;
#endif
- TAILQ_INSERT_TAIL(bucket, c, c_link);
+ TAILQ_INSERT_TAIL(&bucket->cq_q, c, c_link);
+ if (c->c_time < bucket->cq_hint)
+ bucket->cq_hint = c->c_time;
#ifdef CALLWHEEL_STATS
- callwheel_count++;
- callwheel_established++;
- if (++callwheel_sizes[c->c_time & callwheelmask] > callwheel_maxlength)
- callwheel_maxlength =
+ callwheel_count.ev_count++;
+ callwheel_established.ev_count++;
+ if (++callwheel_sizes[c->c_time & callwheelmask] >
+ callwheel_maxlength.ev_count)
+ callwheel_maxlength.ev_count =
callwheel_sizes[c->c_time & callwheelmask];
#endif
@@ -1086,6 +1131,7 @@
static void
callout_stop_locked(struct callout *c)
{
+ struct callout_queue *bucket;
/*
* Don't attempt to delete a callout that's not on the queue.
@@ -1100,10 +1146,13 @@
if (nextsoftcheck == c)
nextsoftcheck = TAILQ_NEXT(c, c_link);
- TAILQ_REMOVE(&callwheel[c->c_time & callwheelmask], c, c_link);
+ bucket = &callwheel[c->c_time & callwheelmask];
+ TAILQ_REMOVE(&bucket->cq_q, c, c_link);
+ if (TAILQ_EMPTY(&bucket->cq_q))
+ bucket->cq_hint = UQUAD_MAX;
#ifdef CALLWHEEL_STATS
- callwheel_count--;
- callwheel_disestablished++;
+ callwheel_count.ev_count--;
+ callwheel_disestablished.ev_count++;
callwheel_sizes[c->c_time & callwheelmask]--;
#endif
@@ -1143,18 +1192,29 @@
splx(s);
printf("Callwheel statistics:\n");
- printf("\tCallouts currently queued: %llu\n", callwheel_count);
- printf("\tCallouts established: %llu\n", callwheel_established);
- printf("\tCallouts disestablished: %llu\n", callwheel_disestablished);
- if (callwheel_changed != 0)
- printf("\t\tOf those, %llu were changes\n", callwheel_changed);
- printf("\tCallouts that fired: %llu\n", callwheel_fired);
+ printf("\tCallouts currently queued: %llu\n",
+ (long long) callwheel_count.ev_count);
+ printf("\tCallouts established: %llu\n",
+ (long long) callwheel_established.ev_count);
+ printf("\tCallouts disestablished: %llu\n",
+ (long long) callwheel_disestablished.ev_count);
+ if (callwheel_changed.ev_count != 0)
+ printf("\t\tOf those, %llu were changes\n",
+ (long long) callwheel_changed.ev_count);
+ printf("\tCallouts that fired: %llu\n",
+ (long long) callwheel_fired.ev_count);
printf("\tNumber of buckets: %d\n", callwheelsize);
- printf("\tNumber of hash collisions: %d\n", callwheel_collisions);
- printf("\tMaximum hash chain length: %d\n", callwheel_maxlength);
+ printf("\tNumber of hash collisions: %llu\n",
+ (long long) callwheel_collisions.ev_count);
+ printf("\tMaximum hash chain length: %llu\n",
+ (long long) callwheel_maxlength.ev_count);
printf("\tSoftclocks: %llu, Softchecks: %llu\n",
Home |
Main Index |
Thread Index |
Old Index