From owner-freebsd-hackers  Sat Feb 26 12:44:44 2000
Delivered-To: freebsd-hackers@freebsd.org
Received: from c62443-a.frmt1.sfba.home.com (c62443-a.frmt1.sfba.home.com [24.0.69.165])
	by hub.freebsd.org (Postfix) with ESMTP id 4CBEC37B5CC
	for <freebsd-hackers@freebsd.org>; Sat, 26 Feb 2000 12:44:39 -0800 (PST)
	(envelope-from adsharma@c62443-a.frmt1.sfba.home.com)
Received: (from adsharma@localhost)
	by c62443-a.frmt1.sfba.home.com (8.9.3/8.9.3) id MAA16383;
	Sat, 26 Feb 2000 12:44:38 -0800
Date: Sat, 26 Feb 2000 12:44:38 -0800
From: Arun Sharma <adsharma@c62443-a.frmt1.sfba.home.com>
Message-Id: <200002262044.MAA16383@c62443-a.frmt1.sfba.home.com>
To: freebsd-hackers@freebsd.org
Subject: Re: 64bit OS? 
In-Reply-To: <200002210620.WAA27921@c62443-a.frmt1.sfba.home.com>
References: <200002200528.QAA04257@mycenae.ilion.eu.org> <200002200653.WAA99167@apollo.backplane.com> <200002210620.WAA27921@c62443-a.frmt1.sfba.home.com>
Reply-To: adsharma@sharmas.dhs.org
Sender: owner-freebsd-hackers@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

Arun Sharma wrote:
> Matt Dillon wrote:
> >     What I would truely love to do would be to get away with not using a GPT
> >     at all and instead doing a vm_map_lookup_entry()/vm_page_lookup()
> >     (essentially taking a vm_fault), then optimize the vm_map_entry 
> >     structural hierarchy to look more like a GPT rather then the linear 
> >     list it currently is.  When coupled with an STLB, especially one that 
> >     can be optimized, I think performance would be extremely good.
> 
> For finding the vm_map_entry for a virtual address, a balanced binary tree 
> works better. Linux does well here - it uses AVL trees, which find the
> right vm_map_entry in O(log n) time.

I just did some investigation into seeing if this (balanced binary trees)
is a useful optimization. It doesn't look like one. 

I instrumented the kernel and collected some stats. On booting the kernel
into KDE and running xemacs and netscape, I got:

kern.vm_map_nsteps: 151916
kern.vm_map_nlookups: 65441

i.e. roughly 3 vm_map_entries were walked before getting to the right one.

Then I did a make clean all; in /usr/src/sys and at the end of the compilation,
I got:

kern.vm_map_nsteps: 666258
kern.vm_map_nlookups: 628911

This time the hints seemed to have worked extremely well and there is almost
no overhead involved.

These numbers would be valid even for 64 bit architectures. However, if
the number of apps which use a large number of shared libraries or loadable
modules (Mozilla with XPCOM, KDE with KOM/DCOP) things can be slightly
different.

For now, I think we're just fine with linear linked lists with a hint.

	-Arun

*** vm_map.c-	Sat Feb 26 12:01:59 2000
--- vm_map.c	Sat Feb 26 12:13:46 2000
***************
*** 75,80 ****
--- 75,83 ----
  #include <sys/mman.h>
  #include <sys/vnode.h>
  #include <sys/resourcevar.h>
+ #include <sys/types.h>
+ #include <sys/linker_set.h>
+ #include <sys/sysctl.h>
  
  #include <vm/vm.h>
  #include <vm/vm_param.h>
***************
*** 331,336 ****
--- 334,349 ----
  #define	SAVE_HINT(map,value) \
  		(map)->hint = (value);
  
+ /* Some counters for tracking the overhead of servicing page faults */
+ static unsigned long nsteps = 0;
+ static unsigned long nlookups = 0;
+ 
+ SYSCTL_LONG(_kern, OID_AUTO, vm_map_nsteps, CTLFLAG_RW, 
+ 	    &nsteps, "");
+ 
+ SYSCTL_LONG(_kern, OID_AUTO, vm_map_nlookups, CTLFLAG_RW, 
+ 	    &nlookups, "");
+ 
  /*
   *	vm_map_lookup_entry:	[ internal use only ]
   *
***************
*** 350,355 ****
--- 363,370 ----
  	vm_map_entry_t cur;
  	vm_map_entry_t last;
  
+ 	nlookups++;
+ 
  	/*
  	 * Start looking either from the head of the list, or from the hint.
  	 */
***************
*** 401,406 ****
--- 416,422 ----
  			break;
  		}
  		cur = cur->next;
+ 		nsteps++;
  	}
  	*entry = cur->prev;
  	SAVE_HINT(map, *entry);


To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-hackers" in the body of the message