X-Recipient: archive-cygwin AT delorie DOT com
X-Spam-Check-By: sourceware.org
From: "Dave Korn" <dave DOT korn AT artimi DOT com>
To: <cygwin AT cygwin DOT com>
References: <6910a60806020741t7ff86d8bgbb7866e62acf1c09 AT mail DOT gmail DOT com> <484411AA DOT AF8A9011 AT dessent DOT net> <026f01c8c4d3$a4309510$2708a8c0 AT CAM DOT ARTIMI DOT COM> <48442EDB DOT 11A94F8 AT dessent DOT net> <027101c8c4db$0027a820$2708a8c0 AT CAM DOT ARTIMI DOT COM> <48443F2A DOT 84F18D1 AT dessent DOT 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
X-Mailer: Microsoft Office Outlook 11
In-Reply-To: <48443F2A.84F18D1@dessent.net>
Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
Precedence: bulk
List-Id: <cygwin.cygwin.com>
List-Unsubscribe: <mailto:cygwin-unsubscribe-archive-cygwin=delorie DOT com AT cygwin DOT com>
List-Subscribe: <mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive: <http://sourceware.org/ml/cygwin/>
List-Post: <mailto:cygwin AT cygwin DOT com>
List-Help: <mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Delivered-To: mailing list cygwin AT cygwin DOT 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/