By aligning n_buckets to power of 2 we can turn the "bucket = hashval %
n_buckets" into a less expensive bucket = hashval & (n_buckets - 1).
This removes the DIV instruction as shown below.
Before:
xor %edx,%edx
divl 0x8(%rbx)
mov %edx,%eax
add $0x1,%rax
shl $0x4,%rax
add %rbx,%rax
After:
lea -0x1(%rdi),%edx
and %edx,%eax
add $0x1,%rax
shl $0x4,%rax
add %rbx,%rax
With a microbenchmark, measuring the time to locate the bucket (i.e.
time_to_calculate_hashval + time_to_calculate_bucket_position) we have
the results below (time in clock cycles):
keylen before after
2-10 79.0 61.9 (-21.65%)
11-17 81.0 64.4 (-20.48%)
18-25 90.0 73.2 (-18.69%)
26-32 104.7 87.0 (-16.82%)
33-40 108.4 89.6 (-17.37%)
41-48 111.2 91.9 (-17.38%)
49-55 120.1 102.1 (-15.04%)
56-63 134.4 115.7 (-13.91%)
As expected the gain is constant, regardless of the key length.
The time to clculate the hashval varies with the key length, which
explains the bigger gains for short keys.
Add static inline function to align a value to it's next power of 2.
This is commonly done by a SWAR like the one in:
http://aggregate.org/MAGIC/#Next Largest Power of 2
However a microbench shows that the implementation herer is a faster.
It doesn't really impact the possible user of this function, but it's
interesting nonetheless.
Using a x86_64 i7 Ivy Bridge it shows a ~4% advantage by using clz
instead instead of the OR and SHL chain. And this is by using a BSR
since Ivy Bridge doesn't have LZCNT. New Haswell processors have the
LZCNT instruction which can make this even better. ARM also has a CLZ
instruction so it should be better, too.
Code used to test:
...
v = val[i];
t1 = get_cycles(0);
a = ALIGN_POWER2(v);
t1 = get_cycles(t1);
t2 = get_cycles(0);
v = nlpo2(v);
t2 = get_cycles(t2);
printf("%u\t%llu\t%llu\t%d\n", v, t1, t2, v == a);
...
In which val is an array of 20 random unsigned int, nlop2 is the SWAR
implementation and get_cycles uses RDTSC to measure the performance.
Averages:
ALIGN_POWER2: 30 cycles
nlop2: 31.4 cycles
During the last merge window (3.12) a couple of modules gained devname
aliases, but without the necessary major and minor information. These were
then silently ignored when generating modules.devname.
Complain loudly to avoid such errors sneaking in undetected in the future:
depmod: ERROR: Module 'zram' has devname (zram) but lacks major and minor information. Ignoring.
depmod: ERROR: Module 'uhid' has devname (uhid) but lacks major and minor information. Ignoring.
Cc: Kay Sievers <kay@vrfy.org>
Cc: Lucas De Marchi <lucas.demarchi@profusion.mobi>
It's used in so many places without checking, that's really pointless to
check for it in macro.h.
Also remove AC_C_TYPEOF from configure.ac since we don't use -ansi.
Commit 8efede20ef ("Use _Static_assert") introduced the usage of
_Static_assert(). However, _Static_assert() is a fairly new thing,
since it was introduced only in gcc 4.6. In order to support older
compilers, this patch adds a configure.in test that checks whether
_Static_assert() is usable or not, and adjust the behavior of the
assert_cc() macro accordingly.
With readdir_r() we should be providing enough space to store the dir
name. This could be accomplished by define an union like systemd does:
union dirent_storage {
struct dirent de;
uint8_t storage[offsetof(struct dirent, d_name) +
((NAME_MAX + 1 + sizeof(long)) & ~(sizeof(long) - 1))];
};
However in all places that we use readdir_r() we have no concerns about
reentrance nor we have problems with threads. Thus use the simpler
readdir() instead.
We also remove the error logging here (that could be added back by
checking errno), but it was not adding much value so it's gone.
stdout and stderr are names reserved for the implementation
and musl uses them rightfully as macro - and the expansion
causes (of course) unexpected results.
rename the struct members stdout to out and stderr
to err, to be 1) compliant 2) cause compilation to
succeed.
fixes build with musl libc.
It occurred to an openSUSE user that our mkinitrd would throw a
warning when used with kmod:
libkmod: conf_files_list: unsupported file mode /dev/null: 0x21b6
Grepping for the error message revealed that there might be a missing
"else" keyword here, since it is unusual to put an "if" directly after
closing brace.
In containers/VM's/initrd one might not have installed any modules and
accompanying modules.devname Don't fail if this is the case, just warn.
When used in systemd this means we don't get a failing unit on booting
containers.
- Fix infinite loop when path is relative
- Fix not considering EEXIST as a success
- General refactor to mkdir_p so it never calls mkdir for an existing
dir (given no one creates it from outside)
Instead of linking dynamically with libkmod, use libkmod-private.la. We
disallow creating a static libkmod because we can't hide symbols there
and it cause problems with external programs. However this should not
prevent users that are only interested in the tools we provide not being
able to ship only them keeping the library alone.
Other projects also do this to allow our tools to use certain functions
that should not be used outside of the project.
The reason to have a kmod-nolib binary is that we need to call kmod on
test cases (or a symlink to it) and for testing things in tree. Since
we are using libtool if we are dinamically linking to libkmod what we
end up having is a shell script that (depending on the version *)
changes argv[0] to contain an "lt-" prefix. Since this screws with our
compat stuff, we had a kmod-nolib that links statically.
This all workaround works fine iff we are using one of the compat
commands, i.e. we are using the symlinks insmod, rmmod, modprobe, etc.
However if we are actually trying the kmod binary, this doesn't work
because we can't create a kmod symlink since there's already a kmod
binary.
So, completely give up on libtool fixing their mess. Now we create a
tool/test/ directory and the symlinks and kmod is put there.
* http://lists.gnu.org/archive/html/bug-libtool/2011-12/msg00023.html
Do the same as done in systemd by Cristian Rodríguez
<crrodriguez@opensuse.org>. We use private symbols, not namespaced. So
don't pretend we support static linking.
Lucas De Marchi
Tom Gundersen
Thomas Petazzoni
John Spencer
Jan Engelhardt