[Omake] SVN Commit: OMake Build System [0.9.8.x] (Rev. 10621)

[Jason Hickey]

On May 3, 2007, at 4:52 PM, Aleksey Nogin wrote:

> On 03.05.2007 16:10, Jason J. Hickey wrote:
>
>> The problem with the new implementation is that the normal  
>> operation, the
>> coarse comparison, now gets a lot of collisions *by definition*.
>
> Huh? Didn't you just solve this by making sure that the coarse hash  
> is available? If the goal is to make the comparisons faster, we do  
> not need to cons-hash, just to include the hash number in the data  
> structure.

No, it makes it better, but not great.  If the hash is perfect, then  
inequalities will be O(1).

The problem is that is isn't a hash-cons, so equality is not O(1).   
It will frequently happen that you have two values that are equal,  
but not pointer equal.

>
>> There is a solution, which is a vertical split, where each fine
>> node has the hash-consed coarse node as a component.  Comparisons
>> should be based on the coarse node, but the full hash-consing would
>> be case-sensitive.
>
> What is the point of cons-hashing the coarse structure and then  
> cons-hashing it _again_ inside the fine structure?
>
> What we may want to do instead, may be, is to change the FileCase.t  
> to be StringHash.t instead of string. This way we'd still get the  
> maximal allowed sharing between the different case-variations of  
> the same filename.

It doesn't matter if it is inside or outside, either way is ok with  
me.  The point is that comparison should be O(1) (I know I'm  
repeating my one track mind:).

So:
    - Given a fine value, you need to be able to get the coarse value  
in time O(1).
    - The coarse value needs to be hash-consed, so that comparison is  
O(1).

It doesn't matter the representation, as long as both operations are O 
(1).  Note that it doesn't cost anything to put the coarse value  
inside the fine one, but no biggie either way.

Jason

--
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257