Skip to content

Commit 757b491

Browse files
webkit-commit-queuehyjorc1
webkit-commit-queue
authored and
hyjorc1
committed
Unreviewed, reverting 266929@main.
https://bugs.webkit.org/show_bug.cgi?id=260353 Regressions Reverted changeset: "[JSC] Introduce wyhash to StringImpl" https://bugs.webkit.org/show_bug.cgi?id=260147 https://commits.webkit.org/266929@main Canonical link: https://commits.webkit.org/267004@main
1 parent e65fa55 commit 757b491

29 files changed

Lines changed: 838 additions & 1993 deletions

‎Source/JavaScriptCore/create_hash_table‎

Lines changed: 52 additions & 204 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
# (c) 2000-2002 by Harri Porten <porten@kde.org> and
66
# David Faure <faure@kde.org>
77
# Modified (c) 2004 by Nikolas Zimmermann <wildfox@kde.org>
8-
# Copyright (C) 2007-2023 Apple Inc. All rights reserved.
8+
# Copyright (C) 2007-2022 Apple Inc. All rights reserved.
99
#
1010
# This library is free software; you can redistribute it and/or
1111
# modify it under the terms of the GNU Lesser General Public
@@ -24,7 +24,6 @@
2424

2525
use strict;
2626
use warnings;
27-
use bigint;
2827
use Getopt::Long qw(:config pass_through);
2928

3029
my $file = shift @ARGV or die("Must provide source file as final argument.");
@@ -47,8 +46,6 @@ my $pefectHashSize;
4746
my $compactSize;
4847
my $compactHashSizeMask;
4948
my $banner = 0;
50-
my $mask64 = 2**64 - 1;
51-
my $mask32 = 2**32 - 1;
5249
sub calcPerfectHashSize();
5350
sub calcCompactHashSize();
5451
sub output();
@@ -197,209 +194,60 @@ sub calcCompactHashSize()
197194
}
198195
}
199196

200-
sub finalizeAndMaskTop8Bits($) {
201-
my ($value) = @_;
202-
203-
$value &= $mask32;
204-
205-
# Force "avalanching" of lower 32 bits
206-
$value ^= leftShift($value, 3);
207-
$value += ($value >> 5);
208-
$value = ($value & $mask32);
209-
$value ^= (leftShift($value, 2) & $mask32);
210-
$value += ($value >> 15);
211-
$value = $value & $mask32;
212-
$value ^= (leftShift($value, 10) & $mask32);
213-
214-
# Save 8 bits for StringImpl to use as flags.
215-
$value &= 0xffffff;
216-
217-
# This avoids ever returning a hash code of 0, since that is used to
218-
# signal "hash not computed yet". Setting the high bit maintains
219-
# reasonable fidelity to a hash code of 0 because it is likely to yield
220-
# exactly 0 when hash lookup masks out the high bits.
221-
$value = (0x80000000 >> 8) if ($value == 0);
222-
223-
return $value;
224-
}
225-
226197
# Paul Hsieh's SuperFastHash
227198
# http://www.azillionmonkeys.com/qed/hash.html
228-
sub superFastHash {
229-
my @chars = @_;
230-
231-
# This hash is designed to work on 16-bit chunks at a time. But since the normal case
232-
# (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
233-
# were 16-bit chunks, which should give matching results
234-
235-
my $hash = 0x9e3779b9;
236-
my $l = scalar @chars; #I wish this was in Ruby --- Maks
237-
my $rem = $l & 1;
238-
$l = $l >> 1;
239-
240-
my $s = 0;
241-
242-
# Main loop
243-
for (; $l > 0; $l--) {
244-
$hash += ord($chars[$s]);
245-
my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
246-
$hash = (leftShift($hash, 16) & $mask32) ^ $tmp;
247-
$s += 2;
248-
$hash += $hash >> 11;
249-
$hash &= $mask32;
250-
}
251-
252-
# Handle end case
253-
if ($rem != 0) {
254-
$hash += ord($chars[$s]);
255-
$hash ^= (leftShift($hash, 11) & $mask32);
256-
$hash += $hash >> 17;
257-
}
258-
259-
return finalizeAndMaskTop8Bits($hash);
260-
}
261-
262-
sub uint64_add($$) {
263-
my ($a, $b) = @_;
264-
my $sum = $a + $b;
265-
return $sum & $mask64;
266-
}
267-
268-
sub uint64_multi($$) {
269-
my ($a, $b) = @_;
270-
my $product = $a * $b;
271-
return $product & $mask64;
272-
}
273-
274-
sub wymum($$) {
275-
my ($A, $B) = @_;
276-
277-
my $ha = $A >> 32;
278-
my $hb = $B >> 32;
279-
my $la = $A & $mask32;
280-
my $lb = $B & $mask32;
281-
my $hi;
282-
my $lo;
283-
my $rh = uint64_multi($ha, $hb);
284-
my $rm0 = uint64_multi($ha, $lb);
285-
my $rm1 = uint64_multi($hb, $la);
286-
my $rl = uint64_multi($la, $lb);
287-
my $t = uint64_add($rl, ($rm0 << 32));
288-
my $c = int($t < $rl);
289-
290-
$lo = uint64_add($t, ($rm1 << 32));
291-
$c += int($lo < $t);
292-
$hi = uint64_add($rh, uint64_add(($rm0 >> 32), uint64_add(($rm1 >> 32), $c)));
293-
294-
return ($lo, $hi);
295-
};
296-
297-
sub wymix($$) {
298-
my ($A, $B) = @_;
299-
($A, $B) = wymum($A, $B);
300-
return $A ^ $B;
301-
}
302-
303-
sub convert32BitTo64Bit($) {
304-
my ($v) = @_;
305-
my ($mask1) = 281470681808895; # 0x0000_ffff_0000_ffff
306-
$v = ($v | ($v << 16)) & $mask1;
307-
my ($mask2) = 71777214294589695; # 0x00ff_00ff_00ff_00ff
308-
return ($v | ($v << 8)) & $mask2;
309-
}
310-
311-
sub convert16BitTo32Bit($) {
312-
my ($v) = @_;
313-
return ($v | ($v << 8)) & 0x00ff_00ff;
314-
}
315-
316-
sub wyhash {
317-
# https://github.com/wangyi-fudan/wyhash
318-
my @chars = @_;
319-
my $charCount = scalar @chars;
320-
my $byteCount = $charCount << 1;
321-
my $charIndex = 0;
322-
my $seed = 0;
323-
my @secret = ( 11562461410679940143, 16646288086500911323, 10285213230658275043, 6384245875588680899 );
324-
my $move1 = (($byteCount >> 3) << 2) >> 1;
325-
326-
$seed ^= wymix($seed ^ $secret[0], $secret[1]);
327-
my $a = 0;
328-
my $b = 0;
329-
330-
local *c2i = sub {
331-
my ($i) = @_;
332-
return ord($chars[$i]);
333-
};
334-
335-
local *wyr8 = sub {
336-
my ($i) = @_;
337-
my $v = c2i($i) | (c2i($i + 1) << 8) | (c2i($i + 2) << 16) | (c2i($i + 3) << 24);
338-
return convert32BitTo64Bit($v);
339-
};
340-
341-
local *wyr4 = sub {
342-
my ($i) = @_;
343-
my $v = c2i($i) | (c2i($i + 1) << 8);
344-
return convert16BitTo32Bit($v);
345-
};
346-
347-
local *wyr2 = sub {
348-
my ($i) = @_;
349-
return c2i($i) << 16;
350-
};
351-
352-
if ($byteCount <= 16) {
353-
if ($byteCount >= 4) {
354-
$a = (wyr4($charIndex) << 32) | wyr4($charIndex + $move1);
355-
$charIndex = $charIndex + $charCount - 2;
356-
$b = (wyr4($charIndex) << 32) | wyr4($charIndex - $move1);
357-
} elsif ($byteCount > 0) {
358-
$a = wyr2($charIndex);
359-
$b = 0;
360-
} else {
361-
$a = $b = 0;
362-
}
363-
} else {
364-
my $i = $byteCount;
365-
if ($i > 48) {
366-
my $see1 = $seed;
367-
my $see2 = $seed;
368-
do {
369-
$seed = wymix(wyr8($charIndex) ^ $secret[1], wyr8($charIndex + 4) ^ $seed);
370-
$see1 = wymix(wyr8($charIndex + 8) ^ $secret[2], wyr8($charIndex + 12) ^ $see1);
371-
$see2 = wymix(wyr8($charIndex + 16) ^ $secret[3], wyr8($charIndex + 20) ^ $see2);
372-
$charIndex += 24;
373-
$i -= 48;
374-
} while ($i > 48);
375-
$seed ^= $see1 ^ $see2;
376-
}
377-
while ($i > 16) {
378-
$seed = wymix(wyr8($charIndex) ^ $secret[1], wyr8($charIndex + 4) ^ $seed);
379-
$i -= 16;
380-
$charIndex += 8;
381-
}
382-
my $move2 = $i >> 1;
383-
$a = wyr8($charIndex + $move2 - 8);
384-
$b = wyr8($charIndex + $move2 - 4);
385-
}
386-
$a ^= $secret[1];
387-
$b ^= $seed;
388-
389-
($a, $b) = wymum($a, $b);
390-
my $hash = wymix($a ^ $secret[0] ^ $byteCount, $b ^ $secret[1]) & $mask32;
391-
392-
return finalizeAndMaskTop8Bits($hash);
393-
}
394-
395199
sub hashValue($) {
396-
my $string = $_[0];
397-
my @chars = split(/ */, $string);
398-
my $charCount = scalar @chars;
399-
if ($charCount <= 48) {
400-
return superFastHash(@chars);
401-
}
402-
return wyhash(@chars);
200+
my @chars = split(/ */, $_[0]);
201+
202+
# This hash is designed to work on 16-bit chunks at a time. But since the normal case
203+
# (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
204+
# were 16-bit chunks, which should give matching results
205+
206+
my $EXP2_32 = 4294967296;
207+
208+
my $hash = 0x9e3779b9;
209+
my $l = scalar @chars; #I wish this was in Ruby --- Maks
210+
my $rem = $l & 1;
211+
$l = $l >> 1;
212+
213+
my $s = 0;
214+
215+
# Main loop
216+
for (; $l > 0; $l--) {
217+
$hash += ord($chars[$s]);
218+
my $tmp = leftShift(ord($chars[$s+1]), 11) ^ $hash;
219+
$hash = (leftShift($hash, 16)% $EXP2_32) ^ $tmp;
220+
$s += 2;
221+
$hash += $hash >> 11;
222+
$hash %= $EXP2_32;
223+
}
224+
225+
# Handle end case
226+
if ($rem != 0) {
227+
$hash += ord($chars[$s]);
228+
$hash ^= (leftShift($hash, 11)% $EXP2_32);
229+
$hash += $hash >> 17;
230+
}
231+
232+
# Force "avalanching" of final 127 bits
233+
$hash ^= leftShift($hash, 3);
234+
$hash += ($hash >> 5);
235+
$hash = ($hash% $EXP2_32);
236+
$hash ^= (leftShift($hash, 2)% $EXP2_32);
237+
$hash += ($hash >> 15);
238+
$hash = $hash% $EXP2_32;
239+
$hash ^= (leftShift($hash, 10)% $EXP2_32);
240+
241+
# Save 8 bits for StringImpl to use as flags.
242+
$hash &= 0xffffff;
243+
244+
# This avoids ever returning a hash code of 0, since that is used to
245+
# signal "hash not computed yet". Setting the high bit maintains
246+
# reasonable fidelity to a hash code of 0 because it is likely to yield
247+
# exactly 0 when hash lookup masks out the high bits.
248+
$hash = (0x80000000 >> 8) if ($hash == 0);
249+
250+
return $hash;
403251
}
404252

405253
sub output() {

‎Source/JavaScriptCore/runtime/JSCBytecodeCacheVersion.cpp.in‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,6 @@
22
#include "JSCBytecodeCacheVersion.h"
33

44
#include "config.h"
5-
#include <wtf/text/SuperFastHash.h>
5+
#include <wtf/text/StringHasher.h>
66

7-
const uint32_t JSCBytecodeCacheVersion = SuperFastHash::computeHash(CACHED_TYPES_CKSUM);
7+
const uint32_t JSCBytecodeCacheVersion = StringHasher::computeHash(CACHED_TYPES_CKSUM);

‎Source/JavaScriptCore/runtime/JSCell.cpp‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
/*
22
* Copyright (C) 1999-2001 Harri Porten (porten@kde.org)
33
* Copyright (C) 2001 Peter Kelly (pmk@post.com)
4-
* Copyright (C) 2003-2023 Apple Inc. All rights reserved.
4+
* Copyright (C) 2003-2020 Apple Inc. All rights reserved.
55
*
66
* This library is free software; you can redistribute it and/or
77
* modify it under the terms of the GNU Library General Public
@@ -299,7 +299,7 @@ NEVER_INLINE NO_RETURN_DUE_TO_CRASH NOT_TAIL_CALLED void reportZappedCellAndCras
299299
MarkedBlock* foundBlock = nullptr;
300300
if (foundBlockHandle) {
301301
foundBlock = &foundBlockHandle->block();
302-
subspaceHash = SuperFastHash::computeHash(foundBlockHandle->subspace()->name());
302+
subspaceHash = StringHasher::computeHash(foundBlockHandle->subspace()->name());
303303
cellSize = foundBlockHandle->cellSize();
304304

305305
variousState |= static_cast<uint64_t>(foundBlockHandle->isFreeListed()) << 0;
@@ -335,7 +335,7 @@ NEVER_INLINE NO_RETURN_DUE_TO_CRASH NOT_TAIL_CALLED void reportZappedCellAndCras
335335
return IterationStatus::Continue;
336336
});
337337
if (foundPreciseAllocation) {
338-
subspaceHash = SuperFastHash::computeHash(foundPreciseAllocation->subspace()->name());
338+
subspaceHash = StringHasher::computeHash(foundPreciseAllocation->subspace()->name());
339339
cellSize = foundPreciseAllocation->cellSize();
340340

341341
variousState |= static_cast<uint64_t>(isFreeListed) << 0;

‎Source/JavaScriptCore/runtime/TemplateObjectDescriptor.h‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
/*
22
* Copyright (C) 2015 Yusuke Suzuki <utatane.tea@gmail.com>.
3-
* Copyright (C) 2019-2023 Apple Inc. All rights reserved.
3+
* Copyright (C) 2019 Apple Inc. All rights reserved.
44
*
55
* Redistribution and use in source and binary forms, with or without
66
* modification, are permitted provided that the following conditions
@@ -97,7 +97,7 @@ inline TemplateObjectDescriptor::TemplateObjectDescriptor(EmptyValueTag)
9797

9898
inline unsigned TemplateObjectDescriptor::calculateHash(const StringVector& rawStrings)
9999
{
100-
SuperFastHash hasher;
100+
StringHasher hasher;
101101
for (const String& string : rawStrings) {
102102
if (string.is8Bit())
103103
hasher.addCharacters(string.characters8(), string.length());

0 commit comments

Comments
 (0)