https://gist.github.com/ilyakurdyukov/f514418f3affd677e1ac408ec0c09188

Skip to content
 
[                    ]
All gists Back to GitHub Sign in Sign up
 
Sign in Sign up
{{ message }}

Instantly share code, notes, and snippets.

@ilyakurdyukov

ilyakurdyukov/faster_lzma_decoder_x86.patch

Last active Dec 13, 2021

  * Star 7
  * Fork 0

Star
Code Revisions 5 Stars 7
Embed
What would you like to do?
">Embed Embed this gist in your website.
Share Copy sharable link for this gist.
Clone via HTTPS Clone with Git or checkout with SVN using the
repository's web address.
 
Learn more about clone URLs
[<script src="https:/]
 
Download ZIP
Faster LZMA decoder for x86 CPUs (patch for XZ Utils).
Raw
faster_lzma_decoder_x86.patch
This file contains bidirectional Unicode text that may be interpreted
or compiled differently than what appears below. To review, open the
file in an editor that reveals hidden Unicode characters. Learn more
about bidirectional Unicode characters
Show hidden characters

 From db71be5c2f77ae18afc73bba85b9c11c6624d243 Mon Sep 17 00:00:00
 2001
 From: Ilya Kurdyukov <jpegqs@gmail.com>
 Date: Mon, 13 Dec 2021 21:25:54 +0700
 Subject: [PATCH] faster lzma_decoder for x86
 Notice: Uses inline assembly with CMOV instruction.
 Another change that removes the comparison with in_size can give a
 few
 percent speedup for architectures with a small number of registers.
 ---
 src/liblzma/lzma/lzma_decoder.c | 78 +++++++++++++-------------
 src/liblzma/rangecoder/range_decoder.h | 51 +++++++++++++++--
 2 files changed, 86 insertions(+), 43 deletions(-)
 diff --git a/src/liblzma/lzma/lzma_decoder.c b/src/liblzma/lzma/
 lzma_decoder.c
 index e605a0a..ecb804b 100644
 --- a/src/liblzma/lzma/lzma_decoder.c
 +++ b/src/liblzma/lzma/lzma_decoder.c
 @@ -415,9 +415,7 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict
 dictptr,
 = offset + match_bit
 + symbol;
 - rc_bit(probs[subcoder_index],
 - offset &= ~match_bit,
 - offset &= match_bit,
 + rc_bit_matched(probs[subcoder_index],
 SEQ_LITERAL_MATCHED);
 // It seems to be faster to do this
 @@ -437,10 +435,7 @@ lzma_decode(void *coder_ptr, lzma_dict
 *restrict dictptr,
 case seq: \
 match_bit = len & offset; \
 subcoder_index = offset + match_bit + symbol; \
 - rc_bit(probs[subcoder_index], \
 - offset &= ~match_bit, \
 - offset &= match_bit, \
 - seq)
 + rc_bit_matched(probs[subcoder_index], seq)
 d(SEQ_LITERAL_MATCHED0);
 len <<= 1;
 @@ -564,40 +559,43 @@ lzma_decode(void *coder_ptr, lzma_dict
 *restrict dictptr,
 probs = coder->pos_special + rep0
 - symbol - 1;
 symbol = 1;
 - offset = 0;
 - case SEQ_DIST_MODEL:
 + offset = 1;
 #ifdef HAVE_SMALL
 + limit = 1 << limit;
 + case SEQ_DIST_MODEL:
 do {
 - rc_bit(probs[symbol], ,
 - rep0 += 1U << offset,
 + rc_bit_dist(probs[symbol],
 + offset,
 SEQ_DIST_MODEL);
 - } while (++offset < limit);
 + offset <<= 1;
 + } while (offset < limit);
 #else
 + case SEQ_DIST_MODEL:
 switch (limit) {
 case 5:
 assert(offset == 0);
 - rc_bit(probs[symbol], ,
 - rep0 += 1U,
 + rc_bit_dist(probs[symbol],
 + offset,
 SEQ_DIST_MODEL);
 - ++offset;
 + offset <<= 1;
 --limit;
 case 4:
 - rc_bit(probs[symbol], ,
 - rep0 += 1U << offset,
 + rc_bit_dist(probs[symbol],
 + offset,
 SEQ_DIST_MODEL);
 - ++offset;
 + offset <<= 1;
 --limit;
 case 3:
 - rc_bit(probs[symbol], ,
 - rep0 += 1U << offset,
 + rc_bit_dist(probs[symbol],
 + offset,
 SEQ_DIST_MODEL);
 - ++offset;
 + offset <<= 1;
 --limit;
 case 2:
 - rc_bit(probs[symbol], ,
 - rep0 += 1U << offset,
 + rc_bit_dist(probs[symbol],
 + offset,
 SEQ_DIST_MODEL);
 - ++offset;
 + offset <<= 1;
 --limit;
 case 1:
 // We need "symbol" only for
 @@ -606,8 +604,8 @@ lzma_decode(void *coder_ptr, lzma_dict *restrict
 dictptr,
 // rc_bit_last() here to omit
 // the unneeded updating of
 // "symbol".
 - rc_bit_last(probs[symbol], ,
 - rep0 += 1U << offset,
 + rc_bit_dist_last(probs[symbol],
 + offset,
 SEQ_DIST_MODEL);
 }
 #endif
 @@ -630,30 +628,32 @@ lzma_decode(void *coder_ptr, lzma_dict
 *restrict dictptr,
 rep0 <<= ALIGN_BITS;
 symbol = 1;
 #ifdef HAVE_SMALL
 - offset = 0;
 + offset = 1;
 case SEQ_ALIGN:
 do {
 - rc_bit(coder->pos_align[
 - symbol], ,
 - rep0 += 1U << offset,
 + rc_bit_dist(coder->pos_align[
 + symbol],
 + offset,
 SEQ_ALIGN);
 - } while (++offset < ALIGN_BITS);
 + offset <<= 1;
 + } while (offset < (1 << ALIGN_BITS));
 #else
 case SEQ_ALIGN0:
 - rc_bit(coder->pos_align[symbol], ,
 - rep0 += 1, SEQ_ALIGN0);
 + rc_bit_dist(coder->pos_align[symbol],
 + 1, SEQ_ALIGN0);
 case SEQ_ALIGN1:
 - rc_bit(coder->pos_align[symbol], ,
 - rep0 += 2, SEQ_ALIGN1);
 + rc_bit_dist(coder->pos_align[symbol],
 + 2, SEQ_ALIGN1);
 case SEQ_ALIGN2:
 - rc_bit(coder->pos_align[symbol], ,
 - rep0 += 4, SEQ_ALIGN2);
 + rc_bit_dist(coder->pos_align[symbol],
 + 4, SEQ_ALIGN2);
 case SEQ_ALIGN3:
 // Like in SEQ_DIST_MODEL, we don't
 // need "symbol" for anything else
 // than indexing the probability array.
 - rc_bit_last(coder->pos_align[symbol], ,
 - rep0 += 8, SEQ_ALIGN3);
 + rc_bit_dist_last(coder->pos_align[
 + symbol],
 + 8, SEQ_ALIGN3);
 #endif
 if (rep0 == UINT32_MAX) {
 diff --git a/src/liblzma/rangecoder/range_decoder.h b/src/liblzma/
 rangecoder/range_decoder.h
 index e0b051f..baec45c 100644
 --- a/src/liblzma/rangecoder/range_decoder.h
 +++ b/src/liblzma/rangecoder/range_decoder.h
 @@ -53,7 +53,8 @@ rc_read_init(lzma_range_decoder *rc, const uint8_t
 *restrict in,
 /// variables `in' and `in_size' to be defined.
 #define rc_to_local(range_decoder, in_pos) \
 lzma_range_decoder rc = range_decoder; \
 - size_t rc_in_pos = (in_pos); \
 + size_t rc_in_pos = in_pos - in_size; \
 + const uint8_t *restrict rc_end = in + in_size; \
 uint32_t rc_bound
 @@ -61,7 +62,7 @@ rc_read_init(lzma_range_decoder *rc, const uint8_t
 *restrict in,
 #define rc_from_local(range_decoder, in_pos) \
 do { \
 range_decoder = rc; \
 - in_pos = rc_in_pos; \
 + in_pos = rc_in_pos + in_size; \
 } while (0)
 @@ -87,12 +88,13 @@ do { \
 #define rc_normalize(seq) \
 do { \
 if (rc.range < RC_TOP_VALUE) { \
 - if (unlikely(rc_in_pos == in_size)) { \
 + if (unlikely(!rc_in_pos)) { \
 coder->sequence = seq; \
 goto out; \
 } \
 + rc.code <<= RC_SHIFT_BITS; \
 rc.range <<= RC_SHIFT_BITS; \
 - rc.code = (rc.code << RC_SHIFT_BITS) | in[rc_in_pos++]; \
 + rc.code |= rc_end[rc_in_pos++]; \
 } \
 } while (0)
 @@ -163,8 +165,49 @@ do { \
 /// statements. On the other hand this also makes it less readable,
 since
 /// spotting the places where the decoder loop may be restarted is
 less
 /// obvious.
 +#if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
 +#define rc_bit_nobranch(prob, pre0, pre1, action0, action1, seq) \
 +do { \
 + rc_normalize(seq); \
 + uint32_t cache = (prob), tmp; \
 + rc_bound = (rc.range >> RC_BIT_MODEL_TOTAL_BITS) * cache; \
 + rc.range -= rc_bound; \
 + /* tmp = rc.code < rc_bound ? rc.range = rc_bound, ~0 : 0; */ \
 + __asm__ ( \
 + "cmpl %3, %2\n\t" \
 + "cmovbl %3, %1\n\t" \
 + "sbbl %0, %0" \
 + : "=&r"(tmp), "+&r"(rc.range) \
 + : "r"(rc.code), "r"(rc_bound) \
 + ); \
 + cache += tmp & ((1 << RC_MOVE_BITS) - 1 - RC_BIT_MODEL_TOTAL); \
 + prob -= cache >> RC_MOVE_BITS; \
 + pre0; tmp = ~tmp; pre1; \
 + rc.code -= tmp & rc_bound; \
 + if (!tmp) { action0; } else { action1; }; \
 +} while (0)
 +#define rc_bit_case(prob, action0, action1, seq) \
 + case seq: rc_bit_nobranch(prob, , symbol = (symbol << 1) - tmp, \
 + action0, action1, seq)
 +#define rc_bit_matched(prob, seq) \
 + rc_bit_nobranch(prob, offset &= match_bit ^ tmp, \
 + symbol = (symbol << 1) - tmp, , , seq)
 +#define rc_bit_dist(prob, offset, seq) \
 + rc_bit_nobranch(prob, , \
 + symbol = (symbol << 1) - tmp; rep0 += offset & tmp, \
 + , , seq);
 +#define rc_bit_dist_last(prob, offset, seq) \
 + rc_bit_nobranch(prob, , rep0 += offset & tmp, , , seq);
 +#else
 #define rc_bit_case(prob, action0, action1, seq) \
 case seq: rc_bit(prob, action0, action1, seq)
 +#define rc_bit_matched(prob, seq) \
 + rc_bit(prob, offset &= ~match_bit, offset &= match_bit, seq)
 +#define rc_bit_dist(prob, offset, seq) \
 + rc_bit(prob, , rep0 += offset, seq);
 +#define rc_bit_dist_last(prob, offset, seq) \
 + rc_bit_last(prob, , rep0 += offset, seq)
 +#endif
 /// Decode a bit without using a probability.
 --
 2.17.1

@amonakov
Copy link

amonakov commented Dec 13, 2021

AMD 4500U (zen 2):
Before:

$ perf stat -r 5 ./src/xzdec/xzdec linux-5.15.tar.xz >/dev/null

 Performance counter stats for './src/xzdec/xzdec linux-5.15.tar.xz' (5 runs):

         11,001.91 msec task-clock:u              #    1.000 CPUs utilized            ( +-  0.06% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
            17,247      page-faults:u             #    1.568 K/sec                    ( +-  0.02% )
    25,839,466,988      cycles:u                  #    2.349 GHz                      ( +-  0.06% )
       570,586,183      stalled-cycles-frontend:u #    2.21% frontend cycles idle     ( +-  0.18% )
     4,603,924,078      stalled-cycles-backend:u  #   17.82% backend cycles idle      ( +-  0.28% )
    33,990,630,407      instructions:u            #    1.32  insn per cycle
                                                  #    0.14  stalled cycles per insn  ( +-  0.00% )
     4,392,930,509      branches:u                #  399.288 M/sec                    ( +-  0.00% )
       448,633,646      branch-misses:u           #   10.21% of all branches          ( +-  0.02% )

          11.00174 +- 0.00639 seconds time elapsed  ( +-  0.06% )

After:

$ perf stat -r 5 ./src/xzdec/xzdec linux-5.15.tar.xz >/dev/null

 Performance counter stats for './src/xzdec/xzdec linux-5.15.tar.xz' (5 runs):

         10,886.97 msec task-clock:u              #    1.000 CPUs utilized            ( +-  0.06% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
            17,250      page-faults:u             #    1.584 K/sec                    ( +-  0.01% )
    25,572,364,776      cycles:u                  #    2.349 GHz                      ( +-  0.06% )
       341,349,770      stalled-cycles-frontend:u #    1.33% frontend cycles idle     ( +-  0.08% )
     9,514,632,432      stalled-cycles-backend:u  #   37.21% backend cycles idle      ( +-  0.16% )
    36,278,706,843      instructions:u            #    1.42  insn per cycle
                                                  #    0.26  stalled cycles per insn  ( +-  0.00% )
     3,759,133,527      branches:u                #  345.287 M/sec                    ( +-  0.00% )
       310,622,266      branch-misses:u           #    8.26% of all branches          ( +-  0.02% )

          10.88696 +- 0.00634 seconds time elapsed  ( +-  0.06% )

Loading

Sorry, something went wrong.

@ilyakurdyukov
Copy link
Author

ilyakurdyukov commented Dec 13, 2021

For this archive, yes, the difference is subtle.

Maybe it's because this hack does not optimize the rc_bit() macro
from SEQ_LITERAL_MATCHED, it can be heavily used for text data (I
guess this archive contains mostly text). But I can try to fix that.

On my Skylake:

perf stat -r 5 build/src/xz/.libs/xz -c -d linux-5.15.7.tar.xz > /dev
/null

Before:

      7 493,13 msec task-clock:u              #    1,000 CPUs utilized            ( +-  0,16% )
             0      context-switches:u        #    0,000 K/sec
             0      cpu-migrations:u          #    0,000 K/sec
        16 469      page-faults:u             #    0,002 M/sec                    ( +-  0,00% )
27 964 283 939      cycles:u                  #    3,732 GHz                      ( +-  0,15% )
33 129 609 542      instructions:u            #    1,18  insn per cycle           ( +-  0,00% )
 4 221 678 998      branches:u                #  563,407 M/sec                    ( +-  0,00% )
   490 799 588      branch-misses:u           #   11,63% of all branches          ( +-  0,02% )

        7,4940 +- 0,0121 seconds time elapsed  ( +-  0,16% )

After:

     7 221,74 msec task-clock:u              #    1,000 CPUs utilized            ( +-  0,29% )
             0      context-switches:u        #    0,000 K/sec
             0      cpu-migrations:u          #    0,000 K/sec
        16 469      page-faults:u             #    0,002 M/sec                    ( +-  0,00% )
26 928 558 378      cycles:u                  #    3,729 GHz                      ( +-  0,26% )
35 371 885 714      instructions:u            #    1,31  insn per cycle           ( +-  0,00% )
 3 572 561 046      branches:u                #  494,695 M/sec                    ( +-  0,00% )
   331 262 037      branch-misses:u           #    9,27% of all branches          ( +-  0,03% )

        7,2223 +- 0,0206 seconds time elapsed  ( +-  0,29% )

Loading

Sorry, something went wrong.

@ilyakurdyukov
Copy link
Author

ilyakurdyukov commented Dec 13, 2021

When I compress Firefox from my system: tar -cf lib.tar /usr/lib/
firefox (which totals in 226549760 bytes), using -7e --format=lzma,
then the difference is bigger (+11%):

Before:

      3 285,02 msec task-clock:u              #    1,000 CPUs utilized            ( +-  0,09% )
             0      context-switches:u        #    0,000 K/sec
             0      cpu-migrations:u          #    0,000 K/sec
         4 181      page-faults:u             #    0,001 M/sec                    ( +-  0,01% )
12 341 894 334      cycles:u                  #    3,757 GHz                      ( +-  0,09% )
13 928 815 327      instructions:u            #    1,13  insn per cycle           ( +-  0,00% )
 1 781 400 452      branches:u                #  542,281 M/sec                    ( +-  0,00% )
   236 255 408      branch-misses:u           #   13,26% of all branches          ( +-  0,02% )

       3,28599 +- 0,00279 seconds time elapsed  ( +-  0,08% )

After:

      2 961,76 msec task-clock:u              #    1,000 CPUs utilized            ( +-  0,03% )
             0      context-switches:u        #    0,000 K/sec
             0      cpu-migrations:u          #    0,000 K/sec
         4 181      page-faults:u             #    0,001 M/sec                    ( +-  0,01% )
11 116 968 963      cycles:u                  #    3,754 GHz                      ( +-  0,03% )
15 027 237 347      instructions:u            #    1,35  insn per cycle           ( +-  0,00% )
 1 474 337 222      branches:u                #  497,791 M/sec                    ( +-  0,00% )
   151 726 579      branch-misses:u           #   10,29% of all branches          ( +-  0,03% )

       2,96238 +- 0,00109 seconds time elapsed  ( +-  0,04% )

But anyway, I need to fix SEQ_LITERAL_MATCHED, which make the patch
bigger, but should make the optimization impact more stable.

Loading

Sorry, something went wrong.

@ilyakurdyukov
Copy link
Author

ilyakurdyukov commented Dec 13, 2021

I have updated the patch, which now includes SEQ_LITERAL_MATCHED, but
the impact on Linux kernel sources hasn't changed.

However, the decompression speed is increased for binary data: 35% ->
39% for the Python3 build directory and 11% -> 15% for Firefox
binaries and data.

Loading

Sorry, something went wrong.

@ilyakurdyukov
Copy link
Author

ilyakurdyukov commented Dec 13, 2021

I made an update that speeds up decompression by 10% for these Linux
kernel sources.

Loading

Sorry, something went wrong.

@cinquemb
Copy link

cinquemb commented Dec 13, 2021

I wonder how it compares with this: http://mattmahoney.net/dc/
text.html

Loading

Sorry, something went wrong.

@haarp
Copy link

haarp commented Dec 13, 2021

Please try to get this patch upstream. There's a lot of energy that
could be saved world-wide with more efficient (de)compression :)

Loading

Sorry, something went wrong.

@amonakov
Copy link

amonakov commented Dec 13, 2021

New 4500U (Zen 2) stats:

 Performance counter stats for './src/xzdec/xzdec linux-5.15.tar.xz' (3 runs):

         10,150.53 msec task-clock:u              #    1.000 CPUs utilized            ( +-  0.29% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
            17,255      page-faults:u             #    1.700 K/sec                    ( +-  0.01% )
    23,828,253,375      cycles:u                  #    2.347 GHz                      ( +-  0.29% )
       236,171,644      stalled-cycles-frontend:u #    0.99% frontend cycles idle     ( +-  0.45% )
    10,985,580,685      stalled-cycles-backend:u  #   46.10% backend cycles idle      ( +-  0.65% )
    37,691,902,062      instructions:u            #    1.58  insn per cycle
                                                  #    0.29  stalled cycles per insn  ( +-  0.00% )
     3,505,241,976      branches:u                #  345.326 M/sec                    ( +-  0.00% )
       207,417,196      branch-misses:u           #    5.92% of all branches          ( +-  0.01% )

           10.1500 +- 0.0299 seconds time elapsed  ( +-  0.29% )

Loading

Sorry, something went wrong.

@amonakov
Copy link

amonakov commented Dec 13, 2021

On Intel i5-2500 (Sandybridge):

Before:

 Performance counter stats for 'src/xzdec/xzdec linux-5.15.tar.xz' (5 runs):

          8,954.71 msec task-clock:u              #    0.998 CPUs utilized            ( +-  0.04% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
             1,368      page-faults:u             #  152.724 /sec                     ( +-  0.26% )
    29,347,257,196      cycles:u                  #    3.277 GHz                      ( +-  0.01% )
    12,337,648,629      stalled-cycles-frontend:u #   42.04% frontend cycles idle     ( +-  0.05% )
     9,029,544,206      stalled-cycles-backend:u  #   30.77% backend cycles idle      ( +-  0.05% )
    33,590,809,450      instructions:u            #    1.14  insn per cycle
                                                  #    0.37  stalled cycles per insn  ( +-  0.00% )
     4,390,208,316      branches:u                #  490.268 M/sec                    ( +-  0.00% )
       477,470,512      branch-misses:u           #   10.88% of all branches          ( +-  0.02% )

           8.97213 +- 0.00262 seconds time elapsed  ( +-  0.03% )

After:

 Performance counter stats for 'src/xzdec/xzdec linux-5.15.tar.xz' (5 runs):

          8,519.22 msec task-clock:u              #    0.994 CPUs utilized            ( +-  0.44% )
                 0      context-switches:u        #    0.000 /sec
                 0      cpu-migrations:u          #    0.000 /sec
             1,358      page-faults:u             #  159.381 /sec                     ( +-  0.11% )
    28,032,300,841      cycles:u                  #    3.290 GHz                      ( +-  0.04% )
    13,667,678,436      stalled-cycles-frontend:u #   48.76% frontend cycles idle     ( +-  0.08% )
     8,181,854,786      stalled-cycles-backend:u  #   29.19% backend cycles idle      ( +-  0.10% )
    37,315,478,332      instructions:u            #    1.33  insn per cycle
                                                  #    0.37  stalled cycles per insn  ( +-  0.00% )
     3,502,520,091      branches:u                #  411.132 M/sec                    ( +-  0.00% )
       224,562,347      branch-misses:u           #    6.41% of all branches          ( +-  0.08% )

           8.57411 +- 0.00504 seconds time elapsed  ( +-  0.06% )

Loading

Sorry, something went wrong.

Sign up for free to join this conversation on GitHub. Already have an
account? Sign in to comment

  * (c) 2021 GitHub, Inc.
  * Terms
  * Privacy
  * Security
  * Status
  * Docs

 

  * Contact GitHub
  * Pricing
  * API
  * Training
  * Blog
  * About

You can't perform that action at this time.
You signed in with another tab or window. Reload to refresh your
session. You signed out in another tab or window. Reload to refresh
your session.