Project

General

Profile

Bug #7655

XIDHASH macro simplification

Added by Marcel Telka over 3 years ago. Updated over 3 years ago.

Status:
Closed
Priority:
Low
Assignee:
Category:
nfs - NFS server and client
Start date:
2016-12-08
Due date:
% Done:

100%

Estimated time:
Difficulty:
Bite-size
Tags:
needs-triage
Gerrit CR:

Description

The XIDHASH macro is defined as follows:

758#if ((DRHASHSZ & (DRHASHSZ - 1)) == 0)
759#define    XIDHASH(xid)    ((xid) & (DRHASHSZ - 1))
760#else
761#define    XIDHASH(xid)    ((xid) % DRHASHSZ)
762#endif

This is an attempt to suggest optimization (by replacing % by &) for special case when DRHASHSZ is 2^X. I believe these days all modern compilers will do such optimization automatically so the XIDHASH macro definition could be simplified and lines 758, 759, 760, and 762 above should be removed.

In addition, if we want to have the XIDHASH macro to produce as even distribution as possible then it looks like it is the best to have the DRHASHSZ set to a prime. In this case the optimized version of XIDHASH at line 759 is never used.


Files

hash.c (128 Bytes) hash.c Marcel Telka, 2016-12-08 08:47 AM

History

#1

Updated by Marcel Telka over 3 years ago

I tested the following simple hash implementation (attached as hash.c):

#include <stdint.h>

uint32_t
hash_and(uint32_t a)
{
        return (a & 255);
}

uint32_t
hash_div(uint32_t a)
{
        return (a % 256);
}

I compiled it 4 times as follows:

/opt/gcc/4.4.4/bin/gcc -Wall -O0 -c -o hash-0.o hash.c
/opt/gcc/4.4.4/bin/gcc -Wall -O1 -c -o hash-1.o hash.c
/opt/gcc/4.4.4/bin/gcc -Wall -O2 -c -o hash-2.o hash.c
/opt/gcc/4.4.4/bin/gcc -Wall -O3 -c -o hash-3.o hash.c

And here are the results produced by gcc:

$ dis hash-0.o
disassembly for hash-0.o

section .text
hash_and()
    hash_and:      55                 pushl  %ebp
    hash_and+0x1:  89 e5              movl   %esp,%ebp
    hash_and+0x3:  8b 45 08           movl   0x8(%ebp),%eax
    hash_and+0x6:  25 ff 00 00 00     andl   $0xff,%eax
    hash_and+0xb:  83 c4 00           addl   $0x0,%esp
    hash_and+0xe:  c9                 leave
    hash_and+0xf:  c3                 ret
hash_div()
    hash_div:      55                 pushl  %ebp
    hash_div+0x1:  89 e5              movl   %esp,%ebp
    hash_div+0x3:  8b 45 08           movl   0x8(%ebp),%eax
    hash_div+0x6:  25 ff 00 00 00     andl   $0xff,%eax
    hash_div+0xb:  83 c4 00           addl   $0x0,%esp
    hash_div+0xe:  c9                 leave
    hash_div+0xf:  c3                 ret
$ dis hash-1.o
disassembly for hash-1.o

section .text
hash_and()
    hash_and:     8b 44 24 04        movl   0x4(%esp),%eax
    hash_and+0x4: 25 ff 00 00 00     andl   $0xff,%eax
    hash_and+0x9: c3                 ret
hash_div()
    hash_div:     8b 44 24 04        movl   0x4(%esp),%eax
    hash_div+0x4: 25 ff 00 00 00     andl   $0xff,%eax
    hash_div+0x9: c3                 ret
$ dis hash-2.o
disassembly for hash-2.o

section .text
hash_and()
    hash_and:     8b 44 24 04        movl   0x4(%esp),%eax
    hash_and+0x4: 25 ff 00 00 00     andl   $0xff,%eax
    hash_and+0x9: c3                 ret
    .text+0xa:    66 90              nop
hash_div()
    hash_div:     8b 44 24 04        movl   0x4(%esp),%eax
    hash_div+0x4: 25 ff 00 00 00     andl   $0xff,%eax
    hash_div+0x9: c3                 ret
$ dis hash-3.o
disassembly for hash-3.o

section .text
hash_and()
    hash_and:     8b 44 24 04        movl   0x4(%esp),%eax
    hash_and+0x4: 25 ff 00 00 00     andl   $0xff,%eax
    hash_and+0x9: c3                 ret
    .text+0xa:    66 90              nop
hash_div()
    hash_div:     8b 44 24 04        movl   0x4(%esp),%eax
    hash_div+0x4: 25 ff 00 00 00     andl   $0xff,%eax
    hash_div+0x9: c3                 ret
$

We can see that for all optimization levels used the compiled assembly is same.

#2

Updated by Marcel Telka over 3 years ago

Here are 64-bit versions:

$ /opt/gcc/4.4.4/bin/gcc -m64 -Wall -O0 -c -o hash-0-64.o hash.c
$ /opt/gcc/4.4.4/bin/gcc -m64 -Wall -O1 -c -o hash-1-64.o hash.c
$ /opt/gcc/4.4.4/bin/gcc -m64 -Wall -O2 -c -o hash-2-64.o hash.c
$ /opt/gcc/4.4.4/bin/gcc -m64 -Wall -O3 -c -o hash-3-64.o hash.c

$ dis hash-0-64.o
disassembly for hash-0-64.o

section .text
hash_and()
    hash_and:      55                 pushq  %rbp
    hash_and+0x1:  48 89 e5           movq   %rsp,%rbp
    hash_and+0x4:  89 7d fc           movl   %edi,-0x4(%rbp)
    hash_and+0x7:  8b 45 fc           movl   -0x4(%rbp),%eax
    hash_and+0xa:  25 ff 00 00 00     andl   $0xff,%eax
    hash_and+0xf:  48 83 c4 00        addq   $0x0,%rsp
    hash_and+0x13: c9                 leave
    hash_and+0x14: c3                 ret
hash_div()
    hash_div:      55                 pushq  %rbp
    hash_div+0x1:  48 89 e5           movq   %rsp,%rbp
    hash_div+0x4:  89 7d fc           movl   %edi,-0x4(%rbp)
    hash_div+0x7:  8b 45 fc           movl   -0x4(%rbp),%eax
    hash_div+0xa:  25 ff 00 00 00     andl   $0xff,%eax
    hash_div+0xf:  48 83 c4 00        addq   $0x0,%rsp
    hash_div+0x13: c9                 leave
    hash_div+0x14: c3                 ret
$ dis hash-1-64.o
disassembly for hash-1-64.o

section .text
hash_and()
    hash_and:     40 0f b6 c7        movzbl %dil,%eax
    hash_and+0x4: c3                 ret
hash_div()
    hash_div:     40 0f b6 c7        movzbl %dil,%eax
    hash_div+0x4: c3                 ret
$ dis hash-2-64.o
disassembly for hash-2-64.o

section .text
hash_and()
    hash_and:     40 0f b6 c7        movzbl %dil,%eax
    hash_and+0x4: c3                 ret
    .text+0x5:    90                 nop
    .text+0x6:    66 2e 0f 1f 84 00  nopw   %cs:0x0(%rax,%rax)
                  00 00 00 00
hash_div()
    hash_div:     40 0f b6 c7        movzbl %dil,%eax
    hash_div+0x4: c3                 ret
$ dis hash-3-64.o
disassembly for hash-3-64.o

section .text
hash_and()
    hash_and:     40 0f b6 c7        movzbl %dil,%eax
    hash_and+0x4: c3                 ret
    .text+0x5:    90                 nop
    .text+0x6:    66 2e 0f 1f 84 00  nopw   %cs:0x0(%rax,%rax)
                  00 00 00 00
hash_div()
    hash_div:     40 0f b6 c7        movzbl %dil,%eax
    hash_div+0x4: c3                 ret
$
#3

Updated by Marcel Telka over 3 years ago

  • Status changed from In Progress to Pending RTI
#4

Updated by Electric Monk over 3 years ago

  • Status changed from Pending RTI to Closed
  • % Done changed from 0 to 100

git commit b7f0713395ae116c0f57e4a7088abbc989470b04

commit  b7f0713395ae116c0f57e4a7088abbc989470b04
Author: Marcel Telka <marcel@telka.sk>
Date:   2016-12-09T15:30:26.000Z

    7655 XIDHASH macro simplification
    Reviewed by: Patrick Mooney <patrick.mooney@joyent.com>
    Reviewed by: Igor Kozhukhov <igor@dilos.org>
    Reviewed by: Eric Sproul <eric.sproul@circonus.com>
    Approved by: Dan McDonald <danmcd@omniti.com>

Also available in: Atom PDF