str==str: compare the first character before calling memcmp()

[vstinner]

BPO	17628
Nosy	@malemburg, @rhettinger, @pitrou, @vstinner, @tiran, @ericsnowcurrently, @serhiy-storchaka
Files	unicode_eq.patch benchmark bench_unicode_eq.py benchmark2 dont_compare_first_last.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2015-03-18.11:06:35.857>
created_at = <Date 2013-04-03.21:29:12.816>
labels = []
title = 'str==str: compare the first character before calling memcmp()'
updated_at = <Date 2015-03-18.11:06:35.856>
user = 'https://github.com/vstinner'

bugs.python.org fields:

activity = <Date 2015-03-18.11:06:35.856>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2015-03-18.11:06:35.857>
closer = 'vstinner'
components = []
creation = <Date 2013-04-03.21:29:12.816>
creator = 'vstinner'
dependencies = []
files = ['29668', '29669', '29671', '29672', '29757']
hgrepos = []
issue_num = 17628
keywords = ['patch']
message_count = 23.0
messages = ['185956', '185957', '185965', '185970', '186007', '186012', '186016', '186017', '186019', '186044', '186045', '186231', '186458', '186464', '186733', '186779', '195234', '195236', '195240', '195241', '195419', '196690', '238417']
nosy_count = 8.0
nosy_names = ['lemburg', 'rhettinger', 'mmokrejs', 'pitrou', 'vstinner', 'christian.heimes', 'eric.snow', 'serhiy.storchaka']
pr_nums = []
priority = 'normal'
resolution = 'out of date'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue17628'
versions = ['Python 3.4']

[vstinner]

In Python 3.4, str==str is implemented by calling memcmp().

unicode_eq() function, used by dict and set types, checks the first byte before calling memcmp(). bytes==bytes uses the same check.

Py_UNICODE_MATCH macro checks the first *and* last character before calling memcmp() since this commit:
---
changeset: 38242:0de9a789de39
branch: legacy-trunk
user: Fredrik Lundh <fredrik@pythonware.com>
date: Tue May 23 10:10:57 2006 +0000
files: Include/unicodeobject.h
description:
needforspeed: check first *and* last character before doing a full memcmp
---

Attached patch changes str==str to check the first and last character before calling memcmp(). It might reduce the overhead of a C function call, but it is much faster when comparing two different strings of the same length with a common prefix (but a different suffix).

The patch merges also unicode_compare_eq() and unicode_eq() to use the same code for str, dict and set.

We may use the same optimization on byte strings.

See also bpo-16321.

[vstinner]

According to my benchmark, performances are almost the same with the patch. The major difference is on comparing two strings longer than 10 characters, of the same length, with a common prefix but a different suffix. See attached benchmark for the result.

[vstinner]

Attach the benchmark script.

[vstinner]

benchmark2: Results on a slower computer. Comparing equal strings is much faster with the patch. Example:

equal, 'A', 1000000 | 945 us (*) | 1.25 ms (+32%)

I don't understand why the patch makes the comparaison much slower, since most time is supposed to be spend in memcmp()?

Is it because I starts at the second character to compare strings, instead of the first character? Memory alignment issue?

[pitrou]

I don't understand why the patch makes the comparaison much slower,
since most time is supposed to be spend in memcmp()?

Because reading the last character evicts useful data from the CPU cache, just before memcmp() reads it again from memory?

In other words, I'm not convinced this is a useful heuristic.

[vstinner]

In other words, I'm not convinced this is a useful heuristic.

Me neither, but we should use the same optimization strategy for all
functions. If we don't compare first and/or last character for
str==str, we should do the same for bytes==bytes and Py_UNICODE_MATCH.

str==str performances depends on the compiler and the libc. So
performances may be very different on Windows, I will try to run the
benchmark on Windows.

GCC has also a known performance issue on memcmp. Its builtin memcmp
implementation is slower than glibc >= 2.10, especiall glibc >= 2.13.
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=43052
"GCC can't beat glibc if function call overhead is low."

2013/4/4 Antoine Pitrou <report@bugs.python.org>:

Antoine Pitrou added the comment:

> I don't understand why the patch makes the comparaison much slower,
> since most time is supposed to be spend in memcmp()?

Because reading the last character evicts useful data from the CPU cache, just before memcmp() reads it again from memory?

In other words, I'm not convinced this is a useful heuristic.

----------

---

Python tracker <report@bugs.python.org>
<http://bugs.python.org/issue17628\>

---

[malemburg]

On 04.04.2013 10:33, STINNER Victor wrote:
>>> I don't understand why the patch makes the comparaison much slower,
>>> since most time is supposed to be spend in memcmp()?
>>
>> Because reading the last character evicts useful data from the CPU cache, just before memcmp() reads it again from memory?
>>
>> In other words, I'm not convinced this is a useful heuristic.

Same here. The heuristic may work for short strings that easily fit
into the CPU cache, but as soon as you use it on longer strings,
this will result in much slower comparisons.

Whether this results in a speedup or not also depends a lot
on the domain of where you need to run comparisons, e.g. if you have
run the heuristic on Python's special method names (such as "__init__")
it won't give you any benefit. OTOH, it's easy to construct strings
that benefit a lot from it :-)

Something that typically works well in practice is to inline
the comparison of the first few characters and then call memcmp()
on the remaining ones. This avoids cache corruption and safes
a few cycles setup costs for memcmp() for short strings.

[vstinner]

By the way, my initial concern was to merge unicode_compare_eq() and
unicode_eq() functions.

unicode_compare_eq() only uses memcmp(), whereas unicode_eq() checks
if the first byte is different before calling memcmp(). So the
question is to decide which one is faster ;-)

[malemburg]

On 04.04.2013 11:21, STINNER Victor wrote:

STINNER Victor added the comment:

By the way, my initial concern was to merge unicode_compare_eq() and
unicode_eq() functions.

unicode_compare_eq() only uses memcmp(), whereas unicode_eq() checks
if the first byte is different before calling memcmp(). So the
question is to decide which one is faster ;-)

The second one was faster a couple of years ago. Things may have
changed since then (better compilers, CPUs, etc.). Perhaps you
could run a benchmark with increasing sizes of strings, one set
with mismatches in the last character, the other with matching
strings.

[ericsnowcurrently]

Marc-Andre Lemburg added the comment:
Same here. The heuristic may work for short strings that easily fit
into the CPU cache, but as soon as you use it on longer strings,
this will result in much slower comparisons.

When testing both, would it help to test the end of the string before the beginning? I'd expect that be more likely to leave the beginning in the cache for any subsequent memcmp() call.

[malemburg]

On 04.04.2013 19:00, Eric Snow wrote:

Eric Snow added the comment:

> Marc-Andre Lemburg added the comment:
> Same here. The heuristic may work for short strings that easily fit
> into the CPU cache, but as soon as you use it on longer strings,
> this will result in much slower comparisons.

When testing both, would it help to test the end of the string before the beginning? I'd expect that be more likely to leave the beginning in the cache for any subsequent memcmp() call.

Again: this depends a lot on what strings you are dealing with. If
you are comparing strings that only vary in the first few characters,
testing the last character first would not be ideal :-)

Given that CPUs are optimized to read ahead in memory, it's always
better to avoid jumping around too much when accessing memory.

http://en.wikipedia.org/wiki/CPU_cache
http://en.wikipedia.org/wiki/Locality_of_reference
http://lwn.net/Articles/252125/

Ideally, you want to stay within a cache line, typically 64 bytes.

[serhiy-storchaka]

Note that unicode_eq() always called after identity check and hash check. I.e. identity check in Victor's patch is redundant and unicode_eq() called only for strings which have the same hash. The probability to have the same first byte and be equal is a great.

unicode_compare_eq() and unicode_eq() are designed for different purposes. They cannot be just merged.

As the optimization for unicode_eq(), I would have suggested a checking of first machine words instead of first bytes, but this trick is too dirty.

[vstinner]

Because most people agree that checking first and/or last byte/character is not a good idea (may be slower), here is a new patch removing code checking first/last byte or character in bytes_richcompare() and unicode_eq().

It removes the usage of the "register" keyword, I read that modern compilers generate worse code when this keyword is used. Register allocators of modern compilers known better than you which variables should use a register.

[pitrou]

Because most people agree that checking first and/or last
byte/character is not a good idea (may be slower), here is a new patch
removing code checking first/last byte or character in
bytes_richcompare() and unicode_eq().

You misunderstood. Checking the first byte is ok, it's checking the last
byte which can misfire.

It removes the usage of the "register" keyword, I read that modern
compilers generate worse code when this keyword is used. Register
allocators of modern compilers known better than you which variables
should use a register.

I think you should open a separate issue to remove all instances of the
"register" keyword in the code base. It has become useless, any modern
compiler will allocate registers by itself, happily ignoring any
"register" hint.

[serhiy-storchaka]

Some crazy ideas.

Try something like this:

    #define BLOCK unsigned long
    if (size >= sizeof(BLOCK)) {
        if (*(BLOCK*)data1 != *(BLOCK*)data2)
            return 0;
        return (memcmp((unsigned char*)data1 + sizeof(BLOCK),
                       (unsigned char*)data2 + sizeof(BLOCK), size) == 0);
    }
    if (*(unsigned char*)data1 != *(unsigned char*)data2)
        return 0;
    return (memcmp(data1, data2, size) == 0);

Or may be unroll memcmp for small size:

    switch (size) {
#if SIZEOF_LONG == 8
        case 7:
            ...
#endif
        case 3:
            ...
        case 2:
            if (((unsigned char*)data1)[1] != ((unsigned char*)data2)[1])
                return 0;
        case 1:
            if (((unsigned char*)data1)[0] != ((unsigned char*)data2)[0])
                return 0;
        case 0:
            return 1;
        default:
            // case for size >= sizeof(BLOCK)
    }