From: "Dave Korn" <dave.korn@artimi.com>
To: <cygwin@cygwin.com>
References: <6910a60806020741t7ff86d8bgbb7866e62acf1c09@mail.gmail.com> <484411AA.AF8A9011@dessent.net> <026f01c8c4d3$a4309510$2708a8c0@CAM.ARTIMI.COM> <48442EDB.11A94F8@dessent.net> <027101c8c4db$0027a820$2708a8c0@CAM.ARTIMI.COM> <48443F2A.84F18D1@dessent.net>
Subject: RE: rebase not compilable
Date: Mon, 2 Jun 2008 20:52:28 +0100
Message-ID: <029501c8c4ea$2fd94a60$2708a8c0@CAM.ARTIMI.COM>
MIME-Version: 1.0
Content-Type: text/plain; 	charset="us-ascii"
Content-Transfer-Encoding: 7bit
In-Reply-To: <48443F2A.84F18D1@dessent.net>
Mailing-List: contact cygwin-help@cygwin.com; run by ezmlm
Precedence: bulk
Sender: cygwin-owner@cygwin.com
Mail-Followup-To: cygwin@cygwin.com

Brian Dessent wrote on 02 June 2008 19:43:

> Dave Korn wrote:
> 
>> Regardless of how well (or poorly) the
>> hash function distributes DLLS into the various buckets, there are only
>> 1024 of them, and we have many DLLs, many of which will occupy multiple
>> buckets; collisions are inevitable.
> 
> First of all, I don't see where this 1024 comes from.  By my reading the
> hash distributes over the range 0x61300000 - 0x712C0000 in 64k
> increments, meaning 4092 buckets.

static unsigned long
compute_dll_image_base (const char *ofile)
{
  unsigned long hash = strhash (ofile);
  return 0x61300000 + ((hash << 16) & 0x0FFC0000);
}
#endif

  Looking at the mask value, it has ten bits set.  Hence 1024 possible
results.  Looking at the 0 bits to the right of them, they are spaced in
1<<18 = 1<<(16+2) = 1<<16 * 1<<2 = 64k * 4 = 256kB units.  I did this in my
head, so I may be having a brain fart for all I know.

> But what I really meant wasn't necessarily to improve the hashing
> function per se but to give it more buckets, a wider range.

  Point, but short of the world moving to 64-bit address space, we're always
likely to run into collisions round the top end of the 2Gb space.

    cheers,
      DaveK
-- 
Can't think of a witty .sigline today....


--
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple
Problem reports:       http://cygwin.com/problems.html
Documentation:         http://cygwin.com/docs.html
FAQ:                   http://cygwin.com/faq/