performance - Enhanced REP MOVSB for memcpy

Question

I would like to use enhanced REP MOVSB (ERMSB) to get a high bandwidth for a custom memcpy.

ERMSB was introduced with the Ivy Bridge microarchitecture. See the section "Enhanced REP MOVSB and STOSB operation (ERMSB)" in the Intel optimization manual if you don't know what ERMSB is.

The only way I know to do this directly is with inline assembly. I got the following function from https://groups.google.com/forum/#!topic/gnu.gcc.help/-Bmlm_EG_fE

static inline void *__movsb(void *d, const void *s, size_t n) {
  asm volatile ("rep movsb"
                : "=D" (d),
                  "=S" (s),
                  "=c" (n)
                : "0" (d),
                  "1" (s),
                  "2" (n)
                : "memory");
  return d;
}

When I use this however, the bandwidth is much less than with memcpy. __movsb gets 15 GB/s and memcpy get 26 GB/s with my i7-6700HQ (Skylake) system, Ubuntu 16.10, DDR4@2400 MHz dual channel 32 GB, GCC 6.2.

Why is the bandwidth so much lower with REP MOVSB? What can I do to improve it?

Here is the code I used to test this.

//gcc -O3 -march=native -fopenmp foo.c
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <stddef.h>
#include <omp.h>
#include <x86intrin.h>

static inline void *__movsb(void *d, const void *s, size_t n) {
  asm volatile ("rep movsb"
                : "=D" (d),
                  "=S" (s),
                  "=c" (n)
                : "0" (d),
                  "1" (s),
                  "2" (n)
                : "memory");
  return d;
}

int main(void) {
  int n = 1<<30;

  //char *a = malloc(n), *b = malloc(n);

  char *a = _mm_malloc(n,4096), *b = _mm_malloc(n,4096);
  memset(a,2,n), memset(b,1,n);

  __movsb(b,a,n);
  printf("%d
", memcmp(b,a,n));

  double dtime;

  dtime = -omp_get_wtime();
  for(int i=0; i<10; i++) __movsb(b,a,n);
  dtime += omp_get_wtime();
  printf("dtime %f, %.2f GB/s
", dtime, 2.0*10*1E-9*n/dtime);

  dtime = -omp_get_wtime();
  for(int i=0; i<10; i++) memcpy(b,a,n);
  dtime += omp_get_wtime();
  printf("dtime %f, %.2f GB/s
", dtime, 2.0*10*1E-9*n/dtime);  
}

---

The reason I am interested in rep movsb is based off these comments

Note that on Ivybridge and Haswell, with buffers to large to fit in MLC you can beat movntdqa using rep movsb; movntdqa incurs a RFO into LLC, rep movsb does not... rep movsb is significantly faster than movntdqa when streaming to memory on Ivybridge and Haswell (but be aware that pre-Ivybridge it is slow!)

What's missing/sub-optimal in this memcpy implementation?

---

Here are my results on the same system from tinymembnech.

 C copy backwards                                     :   7910.6 MB/s (1.4%)
 C copy backwards (32 byte blocks)                    :   7696.6 MB/s (0.9%)
 C copy backwards (64 byte blocks)                    :   7679.5 MB/s (0.7%)
 C copy                                               :   8811.0 MB/s (1.2%)
 C copy prefetched (32 bytes step)                    :   9328.4 MB/s (0.5%)
 C copy prefetched (64 bytes step)                    :   9355.1 MB/s (0.6%)
 C 2-pass copy                                        :   6474.3 MB/s (1.3%)
 C 2-pass copy prefetched (32 bytes step)             :   7072.9 MB/s (1.2%)
 C 2-pass copy prefetched (64 bytes step)             :   7065.2 MB/s (0.8%)
 C fill                                               :  14426.0 MB/s (1.5%)
 C fill (shuffle within 16 byte blocks)               :  14198.0 MB/s (1.1%)
 C fill (shuffle within 32 byte blocks)               :  14422.0 MB/s (1.7%)
 C fill (shuffle within 64 byte blocks)               :  14178.3 MB/s (1.0%)
 ---
 standard memcpy                                      :  12784.4 MB/s (1.9%)
 standard memset                                      :  30630.3 MB/s (1.1%)
 ---
 MOVSB copy                                           :   8712.0 MB/s (2.0%)
 MOVSD copy                                           :   8712.7 MB/s (1.9%)
 SSE2 copy                                            :   8952.2 MB/s (0.7%)
 SSE2 nontemporal copy                                :  12538.2 MB/s (0.8%)
 SSE2 copy prefetched (32 bytes step)                 :   9553.6 MB/s (0.8%)
 SSE2 copy prefetched (64 bytes step)                 :   9458.5 MB/s (0.5%)
 SSE2 nontemporal copy prefetched (32 bytes step)     :  13103.2 MB/s (0.7%)
 SSE2 nontemporal copy prefetched (64 bytes step)     :  13179.1 MB/s (0.9%)
 SSE2 2-pass copy                                     :   7250.6 MB/s (0.7%)
 SSE2 2-pass copy prefetched (32 bytes step)          :   7437.8 MB/s (0.6%)
 SSE2 2-pass copy prefetched (64 bytes step)          :   7498.2 MB/s (0.9%)
 SSE2 2-pass nontemporal copy                         :   3776.6 MB/s (1.4%)
 SSE2 fill                                            :  14701.3 MB/s (1.6%)
 SSE2 nontemporal fill                                :  34188.3 MB/s (0.8%)

Note that on my system SSE2 copy prefetched is also faster than MOVSB copy.

---

In my original tests I did not disable turbo. I disabled turbo and tested again and it does not appear to make much of a difference. However, changing the power management does make a big difference.

When I do

sudo cpufreq-set -r -g performance

I sometimes see over 20 GB/s with rep movsb.

with

sudo cpufreq-set -r -g powersave

the best I see is about 17 GB/s. But memcpy does not seem to be sensitive to the power management.

---

I checked the frequency (using turbostat) with and without SpeedStep enabled, with performance and with powersave for idle, a 1 core load and a 4 core load. I ran Intel's MKL dense matrix multiplication to create a load and set the number of threads using OMP_SET_NUM_THREADS. Here is a table of the results (numbers in GHz).

              SpeedStep     idle      1 core    4 core
powersave     OFF           0.8       2.6       2.6
performance   OFF           2.6       2.6       2.6
powersave     ON            0.8       3.5       3.1
performance   ON            3.5       3.5       3.1

This shows that with powersave even with SpeedStep disabled the CPU still clocks down to the idle frequency of 0.8 GHz. It's only with performance without SpeedStep that the CPU runs at a constant frequency.

I used e.g sudo cpufreq-set -r performance (because cpufreq-set was giving strange results) to change the power settings. This turns turbo back on so I had to disable turbo after.

Answer 1

This is a topic pretty near to my heart and recent investigations, so I'll look at it from a few angles: history, some technical notes (mostly academic), test results on my box, and finally an attempt to answer your actual question of when and where rep movsb might make sense.

Partly, this is a call to share results - if you can run Tinymembench and share the results along with details of your CPU and RAM configuration it would be great. Especially if you have a 4-channel setup, an Ivy Bridge box, a server box, etc.

History and Official Advice

The performance history of the fast string copy instructions has been a bit of a stair-step affair - i.e., periods of stagnant performance alternating with big upgrades that brought them into line or even faster than competing approaches. For example, there was a jump in performance in Nehalem (mostly targeting startup overheads) and again in Ivy Bridge (most targeting total throughput for large copies). You can find decade-old insight on the difficulties of implementing the rep movs instructions from an Intel engineer in this thread.

For example, in guides preceding the introduction of Ivy Bridge, the typical advice is to avoid them or use them very carefully¹.

The current (well, June 2016) guide has a variety of confusing and somewhat inconsistent advice, such as²:

The specific variant of the implementation is chosen at execution time based on data layout, alignment and the counter (ECX) value. For example, MOVSB/STOSB with the REP prefix should be used with counter value less than or equal to three for best performance.

So for copies of 3 or less bytes? You don't need a rep prefix for that in the first place, since with a claimed startup latency of ~9 cycles you are almost certainly better off with a simple DWORD or QWORD mov with a bit of bit-twiddling to mask off the unused bytes (or perhaps with 2 explicit byte, word movs if you know the size is exactly three).

They go on to say:

String MOVE/STORE instructions have multiple data granularities. For efficient data movement, larger data granularities are preferable. This means better efficiency can be achieved by decomposing an arbitrary counter value into a number of double words plus single byte moves with a count value less than or equal to 3.

This certainly seems wrong on current hardware with ERMSB where rep movsb is at least as fast, or faster, than the movd or movq variants for large copies.

In general, that section (3.7.5) of the current guide contains a mix of reasonable and badly obsolete advice. This is common throughput the Intel manuals, since they are updated in an incremental fashion for each architecture (and purport to cover nearly two decades worth of architectures even in the current manual), and old sections are often not updated to replace or make conditional advice that doesn't apply to the current architecture.

They then go on to cover ERMSB explicitly in section 3.7.6.

I won't go over the remaining advice exhaustively, but I'll summarize the good parts in the "why use it" below.

Other important claims from the guide are that on Haswell, rep movsb has been enhanced to use 256-bit operations internally.

Technical Considerations

This is just a quick summary of the underlying advantages and disadvantages that the rep instructions have from an implementation standpoint.

Advantages for rep movs

1. When a rep movs instruction is issued, the CPU knows that an entire block of a known size is to be transferred. This can help it optimize the operation in a way that it cannot with discrete instructions, for example:

   • Avoiding the RFO request when it knows the entire cache line will be overwritten.
   • Issuing prefetch requests immediately and exactly. Hardware prefetching does a good job at detecting memcpy-like patterns, but it still takes a couple of reads to kick in and will "over-prefetch" many cache lines beyond the end of the copied region. rep movsb knows exactly the region size and can prefetch exactly.

2. Apparently, there is no guarantee of ordering among the stores within³ a single rep movs which can help simplify coherency traffic and simply other aspects of the block move, versus simple mov instructions which have to obey rather strict memory ordering⁴.

3. In principle, the rep movs instruction could take advantage of various architectural tricks that aren't exposed in the ISA. For example, architectures may have wider internal data paths that the ISA exposes⁵ and rep movs could use that internally.

Disadvantages

1. rep movsb must implement a specific semantic which may be stronger than the underlying software requirement. In particular, memcpy forbids overlapping regions, and so may ignore that possibility, but rep movsb allows them and must produce the expected result. On current implementations mostly affects to startup overhead, but probably not to large-block throughput. Similarly, rep movsb must support byte-granular copies even if you are actually using it to copy large blocks which are a multiple of some large power of 2.

2. The software may have information about alignment, copy size and possible aliasing that cannot be communicated to the hardware if using rep movsb. Compilers can often determine the alignment of memory blocks⁶ and so can avoid much of the startup work that rep movs must do on every invocation.

Test Results

Here are test results for many different copy methods from tinymembench on my i7-6700HQ at 2.6 GHz (too bad I have the identical CPU so we aren't getting a new data point...):

 C copy backwards                                     :   8284.8 MB/s (0.3%)
 C copy backwards (32 byte blocks)                    :   8273.9 MB/s (0.4%)
 C copy backwards (64 byte blocks)                    :   8321.9 MB/s (0.8%)
 C copy                                               :   8863.1 MB/s (0.3%)
 C copy prefetched (32 bytes step)                    :   8900.8 MB/s (0.3%)
 C copy prefetched (64 bytes step)                    :   8817.5 MB/s (0.5%)
 C 2-pass copy                                        :   6492.3 MB/s (0.3%)
 C 2-pass copy prefetched (32 bytes step)             :   6516.0 MB/s (2.4%)
 C 2-pass copy prefetched (64 bytes step)             :   6520.5 MB/s (1.2%)
 ---
 standard memcpy                                      :  12169.8 MB/s (3.4%)
 standard memset                                      :  23479.9 MB/s (4.2%)
 ---
 MOVSB copy                                           :  10197.7 MB/s (1.6%)
 MOVSD copy                                           :  10177.6 MB/s (1.6%)
 SSE2 copy                                            :   8973.3 MB/s (2.5%)
 SSE2 nontemporal copy                                :  12924.0 MB/s (1.7%)
 SSE2 copy prefetched (32 bytes step)                 :   9014.2 MB/s (2.7%)
 SSE2 copy prefetched (64 bytes step)                 :   8964.5 MB/s (2.3%)
 SSE2 nontemporal copy prefetched (32 bytes step)     :  11777.2 MB/s (5.6%)
 SSE2 nontemporal copy prefetched (64 bytes step)     :  11826.8 MB/s (3.2%)
 SSE2 2-pass copy                                     :   7529.5 MB/s (1.8%)
 SSE2 2-pass copy prefetched (32 bytes step)          :   7122.5 MB/s (1.0%)
 SSE2 2-pass copy prefetched (64 bytes step)          :   7214.9 MB/s (1.4%)
 SSE2 2-pass nontemporal copy                         :   4987.0 MB/s

Some key takeaways:

• The rep movs methods are faster than all the other methods which aren't "non-temporal"⁷, and considerably faster than the "C" approaches which copy 8 bytes at a time.
• The "non-temporal" methods are faster, by up to about 26% than the rep movs ones - but that's a much smaller delta than the one you reported (26 GB/s vs 15 GB/s = ~73%).
• If you are not using non-temporal stores, using 8-byte copies from C is pretty much just as good as 128-bit wide SSE load/stores. That's because a good copy loop can generate enough memory pressure to saturate the bandwidth (e.g., 2.6 GHz * 1 store/cycle * 8 bytes = 26 GB/s for stores).
• There are no explicit 256-bit algorithms in tinymembench (except probably the "standard" memcpy) but it probably doesn't matter due to the above note.
• The increased throughput of the non-temporal store approaches over the temporal ones is about 1.45x, which is very close to the 1.5x you would expect if NT eliminates 1 out of 3 transfers (i.e., 1 read, 1 write for NT vs 2 reads, 1 write). The rep movs approaches lie in the middle.
• The combination of fairly low memory latency and modest 2-channel bandwidth means this particular chip happens to be able to saturate its memory bandwidth from a single-thread, which changes the behavior dramatically.
• rep movsd seems to use the same magic as rep movsb on this chip. That's interesting because ERMSB only explicitly targets movsb and earlier tests on earlier archs with ERMSB show movsb performing much faster than movsd. This is mostly academic since movsb is more general than movsd anyway.

Haswell

Looking at the Haswell results kindly provided by iwillnotexist in the comments, we see the same general trends (most relevant results extracted):

 C copy                                               :   6777.8 MB/s (0.4%)
 standard memcpy                                      :  10487.3 MB/s (0.5%)
 MOVSB copy                                           :   9393.9 MB/s (0.2%)
 MOVSD copy                                           :   9155.0 MB/s (1.6%)
 SSE2 copy                                            :   6780.5 MB/s (0.4%)
 SSE2 nontemporal copy                                :  10688.2 MB/s (0.3%)

The rep movsb approach is still slower than the non-temporal memcpy, but only by about 14% here (compared to ~26% in the Skylake test). The advantage of the NT techniques above their temporal cousins is now ~57%, even a bit more than the theoretical benefit of the bandwidth reduction.

When should you use rep movs?

Finally a stab at your actual question: when or why should you use it? It draw on the above and introduces a few new ideas. Unfortunately there is no simple answer: you'll have to trade off various factors, including some which you probably can't even know exactly, such as future developments.

A note that the alternative to rep movsb may be the optimized libc memcpy (including copies inlined by the compiler), or it may be a hand-rolled memcp