[Development] What's our policy on changing the result of qHash(T, 0) between major releases?
Thiago Macieira
thiago.macieira at intel.com
Wed Feb 7 07:44:52 CET 2024
On Tuesday, 6 February 2024 22:02:11 PST Marc Mutz via Development wrote:
> As someone who argues that qHash("Hello"_L1) be restored to
> qHash(u"Hello"_s) after this relation was broken somewhere in Qt 5, how
> could I argue against it? :)
It was commit ea8e48a6799cf742ea23f4a30dcfc38a4988fe56 in 5.3.0.
commit ea8e48a6799cf742ea23f4a30dcfc38a4988fe56
Author: Thiago Macieira <thiago.macieira at intel.com>
Date: Thu Dec 19 23:32:04 2013 -0800
Update the qHash function for strings to use the CRC32 instruction
According to my profiling of Qt Creator, qHash and the SHA-1 calculation
are the hottest spots remaining in QtCore. The current qHash function is
not really vectorizable. We could come up with a different algorithm
that is more SIMD-friendly, but since we have the CRC32 instruction that
can read 32- and 64-bit entities, we're set.
This commit also updates the benchmark for QHash and benchmarks both
the hashing function itself and the QHash class. The updated
benchmarks for the CRC32 on my machine shows that the hashing function
is *always* improved, but the hashing isn't always. In particular, the
current algorithm is better for the "numbers" case, for which the data
sample differs in very few bits. The new code is 33% slower for that
particular case.
On average, the improvement (including the "numbers" case) is:
compared to qHash only QHash
Qt 5.0 function 2.54x 1.06x
Qt 4.x function 4.34x 1.34x
Java function 2.71x 1.11x
Now (current = siphash & murmurhash; nonzero_curent = aeshash; we don't have
the CRC32 algorithm any more):
RESULT : tst_QHash::hashing_qt4():"numbers":
126,800.35305 CPU cycles per iteration, 4.66 GHz
470,120.00894 instructions per iteration, 3.708 instr/cycle
RESULT : tst_QHash::hashing_qt50():"numbers":
83,198.10215 CPU cycles per iteration, 4.64 GHz
365,099.00604 instructions per iteration, 4.388 instr/cycle
RESULT : tst_QHash::hashing_current():"numbers":
151,220.07727 CPU cycles per iteration, 4.66 GHz
615,149.01052 instructions per iteration, 4.068 instr/cycle
RESULT : tst_QHash::hashing_nonzero_current():"numbers":
65,224.59934 CPU cycles per iteration, 4.45 GHz
235,073.00508 instructions per iteration, 3.604 instr/cycle
So even the pathological "numbers" case is now faster by about 27%.
With "typical" data ("paths-small"):
qt4: 23,848.939476 CPU cycles per iteration
qt50: 11,681.268231 CPU cycles per iteration
current: 10,623.703491 CPU cycles per iteration
aeshash: 2,870.472204 CPU cycles per iteration
The siphash/murmurhash implementation is slightly faster than the Qt 5.0
implementation and both are over twice as fast as the 4.x implementation. The
aeshash is on average 3.7x faster than even those two.
And with very long data ("longstrings-list"):
qt4: 397,145.21743 CPU cycles per iteration
qt50: 225,105.45316 CPU cycles per iteration
siphash: 102,900.78968 CPU cycles per iteration
aeshash: 10,249.00974 CPU cycles per iteration
That's 10x faster on my laptop, which has 256-bit AES. With just 128-bit AES,
my Skylake workstation is doing about 3.5x better than siphash for this case.
See more numbers in
https://codereview.qt-project.org/c/qt/qtbase/+/537009
--
Thiago Macieira - thiago.macieira (AT) intel.com
Cloud Software Architect - Intel DCAI Cloud Engineering
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5152 bytes
Desc: not available
URL: <http://lists.qt-project.org/pipermail/development/attachments/20240206/4f799a3f/attachment-0001.bin>
More information about the Development
mailing list