linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: "George Spelvin" <linux@sciencehorizons.net>
To: eric.dumazet@gmail.com, Jason@zx2c4.com
Cc: ak@linux.intel.com, davem@davemloft.net, David.Laight@aculab.com,
	djb@cr.yp.to, ebiggers3@gmail.com, hannes@stressinduktion.org,
	jeanphilippe.aumasson@gmail.com,
	kernel-hardening@lists.openwall.com,
	linux-crypto@vger.kernel.org, linux-kernel@vger.kernel.org,
	linux@sciencehorizons.net, luto@amacapital.net,
	netdev@vger.kernel.org, tom@herbertland.com,
	torvalds@linux-foundation.org, tytso@mit.edu,
	vegard.nossum@gmail.com
Subject: Re: HalfSipHash Acceptable Usage
Date: 21 Dec 2016 13:37:51 -0500	[thread overview]
Message-ID: <20161221183751.1123.qmail@ns.sciencehorizons.net> (raw)
In-Reply-To: <1482335804.8944.44.camel@edumazet-glaptop3.roam.corp.google.com>

Eric Dumazet wrote:
> Now I am quite confused.
>
> George said :
>> Cycles per byte on 1024 bytes of data:
>>                       Pentium Core 2  Ivy
>>                       4       Duo     Bridge
>> SipHash-2-4           38.9     8.3     5.8
>> HalfSipHash-2-4       12.7     4.5     3.2
>> MD5                    8.3     5.7     4.7
>
> That really was for 1024 bytes blocks, so pretty much useless for our
> discussion ?

No, they're actually quite relevant, but you have to interpret them
correctly.  I thought I explained in the text following that table,
but let me make it clearer:

To find the time to compute the SipHash of N bytes, round (N+17) up to
the next multiple of 8 bytes and multiply by the numbers above.

To find the time to compute the HalfSipHash of N bytes, round (N+9) up to
the next multiple of 4 bytes and multiply by the numbers above.

To find the time to compute the MD5 of N bytes, round (N+9) up to the
next multiple of 64 bytes and multiply by the numbers above.

It's the different rounding rules that make all the difference.  For small
input blocks, SipHash can be slower per byte yet still faster because
it hashes fewer bytes.

> Reading your numbers last week, I thought SipHash was faster, but George
> numbers are giving the opposite impression.

SipHash annihilates the competition on 64-bit superscalar hardware.
SipHash dominates the field on 64-bit in-order hardware.
SipHash wins easily on 32-bit hardware *with enough registers*.
On register-starved 32-bit machines, it really struggles.

As I explained, in that last case, SipHash barely wins at all.
(On a P4, it actually *loses* to MD5, not that anyone cares.  Running
on a P4 and caring about performance are mutually exclusive.)

  parent reply	other threads:[~2016-12-21 18:37 UTC|newest]

Thread overview: 25+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-12-19 17:32 Jason A. Donenfeld
     [not found] ` <CAGiyFdduUNSGq24zfsk0ZU=hnOCmewAw8vw6XvDoS-3f+3UPKQ@mail.gmail.com>
2016-12-19 21:00   ` Jason A. Donenfeld
2016-12-20 21:36 ` Theodore Ts'o
2016-12-20 23:07   ` George Spelvin
2016-12-20 23:55   ` Eric Dumazet
2016-12-21  3:28     ` George Spelvin
2016-12-21  5:29       ` Eric Dumazet
2016-12-21  6:34         ` George Spelvin
2016-12-21 14:24           ` Jason A. Donenfeld
2016-12-21 15:55             ` George Spelvin
2016-12-21 16:37               ` Jason A. Donenfeld
2016-12-21 16:41               ` [kernel-hardening] " Rik van Riel
2016-12-21 17:25               ` Linus Torvalds
2016-12-21 18:07                 ` George Spelvin
2016-12-22  1:54                 ` Andy Lutomirski
2016-12-21 14:42         ` Jason A. Donenfeld
2016-12-21 15:56           ` Eric Dumazet
2016-12-21 16:33             ` Jason A. Donenfeld
2016-12-21 16:39             ` [kernel-hardening] " Rik van Riel
2016-12-21 17:08               ` Eric Dumazet
2016-12-21 18:37             ` George Spelvin [this message]
2016-12-21 18:40               ` Jason A. Donenfeld
2016-12-21 22:27               ` Theodore Ts'o
2016-12-22  0:18                 ` George Spelvin
2016-12-22  1:13                 ` George Spelvin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20161221183751.1123.qmail@ns.sciencehorizons.net \
    --to=linux@sciencehorizons.net \
    --cc=David.Laight@aculab.com \
    --cc=Jason@zx2c4.com \
    --cc=ak@linux.intel.com \
    --cc=davem@davemloft.net \
    --cc=djb@cr.yp.to \
    --cc=ebiggers3@gmail.com \
    --cc=eric.dumazet@gmail.com \
    --cc=hannes@stressinduktion.org \
    --cc=jeanphilippe.aumasson@gmail.com \
    --cc=kernel-hardening@lists.openwall.com \
    --cc=linux-crypto@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=luto@amacapital.net \
    --cc=netdev@vger.kernel.org \
    --cc=tom@herbertland.com \
    --cc=torvalds@linux-foundation.org \
    --cc=tytso@mit.edu \
    --cc=vegard.nossum@gmail.com \
    --subject='Re: HalfSipHash Acceptable Usage' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).