Slow-paths in GNU libc strstr

I've observed that some patterns issued to strstr cause significant slowdown.

Sample program kill-strstr.c executes strstr(data, pattern), where data is a large string (16MB) filled with character ?; patterns are read from command line.

On my machine following times were recorded:

1. searching string 'johndoe'...
        time: 0.032
2. searching string '??????????????????a'...
        time: 0.050
3. searching string '??????????????????????????????a'...
        time: 0.049
4. searching string '???????????????????????????????a'...
        time: 0.274
5. searching string '??????????????????????????????a?'...
        time: 0.356
6. searching string '??????????????????????????????a??????????????????????????????'...
        time: 0.396

• Slowdown is visible in case 4 (5 times slower than pattern 3). Pattern has 32 characters, and contains '?', except last char.
• Even bigger slowdown occurs in case 5 (7 times slower). This pattern also contains 32 chars, but position of the single letter 'a' is last but one.
• Similar slowdown occurs in case 5 (nearly 8 times slower). In this pattern single letter 'a' is surrounded by 30 '?'.

Penalties of errors in SSE floating point calculations

SSE provides not widely known control register, called MXCSR. This register plays three roles:

1. controls calculations:
• flag "flush to zero" (described later)
• flag "denormals are zeros" (described later)
• rounding mode (not covered in this text)
2. allow to mask/unmask floating-point exceptions
3. save information about floating-point errors - these flags are sticky, i.e. the programmer is responsible for clearing them.

Floating point errors may cause significant slowdown, some of the flags can silence errors makes a program faster. Read more ...

x86 - ISA where 80% of instructons are unimportant

Few years ago I counted instructions from many Linux binaries --- 2014 is good year to repeated this experiment and see that nothing has changed.

I use 32-bit Debian, my installation has been updated few months ago. All files from /usr/bin and all *.so files from /usr/lib was disassembled with objdump (5050 files were processed). Instructions were grouped simply by mnemonic name, taking into account all addressing and encoding modes would be overkill. I've published script that does the job.

Short summary

• Number of distinct decoded instructions is around 650. Since objdump use AT&T syntax, same opcode is seen under different mnemonics, for example mov is saved as movw, movb, movl depending on argument size.
• Total number of x86 instructions is around 750. Read: one hundred instructions never appeared in the binaries.
• There are 81 instructions used just once. For example quite useful CMPPD.
• There are 22 instructions used twice. For example MFENCE --- no one aware of memory ordering?
• There are 15 instructions used three times. For example BTC, but bit manipulating operations are useless.
• 81 plus 22 plus 15 is 118. Another hundred of useless stuff.

Lets look at top 15 rows from detailed results, i.e. instruction with frequency grater than 1%:

• The total count of these instructions is 87.84% of all instructions (almost all, isn't it?).
• The most frequently used instruction is data transfer (mov/movl) --- 42%
• Control flow instructions (call/ret/jmp) --- 13%.
• Conditions (cmp/test/condition jumps: je/jne) --- 10%.
• Basic arithmetic (add/sub/lea) --- 12%
• Simple stack operations (push/pop) --- 6%

Very interesting observation is that conditions are mostly based on je/jne, i.e. jump if zero/jump if not zero.

First FPU instruction appear at 28-th position. First integer SSE appear at 167-th position. First SSE instruction operating on packed floats appear at 315-th position.

Detailed results

Whole table as txt file.

instruction	count	%
mov	5934098	37.63%
call	1414355	8.97%
lea	1071501	6.79%
movl	760677	4.82%
push	655921	4.16%
jmp	611540	3.88%
add	560517	3.55%
je	490250	3.11%
test	475899	3.02%
pop	441608	2.80%
sub	366228	2.32%
cmp	326379	2.07%
jne	264110	1.67%
nop	242356	1.54%
ret	238569	1.51%
xor	148194	0.94%
movzbl	122730	0.78%
and	88863	0.56%
xchg	66885	0.42%
cmpl	64907	0.41%
movzwl	64589	0.41%
movb	57247	0.36%
or	52138	0.33%
shl	50908	0.32%
cmpb	50152	0.32%
jle	41083	0.26%
leave	39923	0.25%
fldl	37428	0.24%
fstpl	37368	0.24%
shr	36503	0.23%
jbe	32866	0.21%
ja	32333	0.21%
sar	30917	0.20%
flds	29672	0.19%
subl	27636	0.18%
setne	27626	0.18%
testb	27420	0.17%
addl	25906	0.16%
imul	25569	0.16%
jg	24796	0.16%
fstp	24349	0.15%
fxch	23464	0.15%
js	21550	0.14%
fstps	21248	0.13%
sbb	16607	0.11%
inc	16200	0.10%
lock	16049	0.10%
jae	14825	0.09%
sahf	14765	0.09%
dec	14276	0.09%
fnstsw	14026	0.09%
sete	13902	0.09%
movw	13895	0.09%
adc	13640	0.09%
jb	12467	0.08%
jl	11700	0.07%
repz	11178	0.07%
fldcw	11110	0.07%
jge	11019	0.07%
movswl	10816	0.07%
fildl	8852	0.06%
cmpw	7601	0.05%
jns	7490	0.05%
fldz	7331	0.05%
fmul	7229	0.05%
out	7203	0.05%
not	7028	0.04%
movsbl	6720	0.04%
in	6503	0.04%
fld	6309	0.04%
faddp	6254	0.04%
fstl	5760	0.04%
fucom	5753	0.04%
neg	5725	0.04%
fucompp	5354	0.03%
rep	5059	0.03%
fmuls	5039	0.03%
pushl	4430	0.03%
jp	4424	0.03%
fnstcw	4400	0.03%
fld1	4176	0.03%
fmulp	4133	0.03%
orl	3927	0.02%
fadds	3789	0.02%
movq	3779	0.02%
fistpl	3709	0.02%
cltd	3597	0.02%
fmull	3313	0.02%
stos	3298	0.02%
lret	3183	0.02%
scas	3103	0.02%
lods	3066	0.02%
cwtl	3064	0.02%
fadd	2852	0.02%
fucomp	2678	0.02%
orb	2481	0.02%
fildll	2418	0.02%
andl	2379	0.02%
setb	2337	0.01%
andb	2263	0.01%
552 rows more...

I accidentally created an infinite loop

I needed to iterate through all values of 32-bit unsigned integer, so I wrote:

#include <stdint.h>
for (uint32_t i=0; i <= UINT32_MAX; i++) {
   // whatever
}

Is it ok? No, because value of uint32_t will never exceed UINT32_MAX = 0xffffffff. Of course we can use larger types, like uint64_t, but on 32-bit machines this requires some additional instructions. For example gcc 4.7 compiled following code:

void loop1(void (*fun)()) {
 for (uint64_t i=0; i <= UINT32_MAX; i++) {
  fun();
 }
}

to:

00000000 :
   0:   57                      push   %edi
   1:   bf 01 00 00 00          mov    $0x1,%edi
   6:   56                      push   %esi
   7:   31 f6                   xor    %esi,%esi
   9:   53                      push   %ebx
   a:   8b 5c 24 10             mov    0x10(%esp),%ebx
   e:   66 90                   xchg   %ax,%ax
  10:   ff d3                   call   *%ebx
  12:   83 c6 ff                add    $0xffffffff,%esi
  15:   83 d7 ff                adc    $0xffffffff,%edi
  18:   89 f8                   mov    %edi,%eax
  1a:   09 f0                   or     %esi,%eax
  1c:   75 f2                   jne    10 
  1e:   5b                      pop    %ebx
  1f:   5e                      pop    %esi
  20:   5f                      pop    %edi
  21:   c3                      ret    

TBH, I have no idea, why such weird sequence has been generated (add, adc, or, jnz). The simplest and portable solution is to detect wrap-around 32-bit value after increment:

uint32_t i=0;
while (1) {
 // loop body

 i += 1;
 if (i == 0) // wrap-around
  break;
}

In assembly code it's even simpler, because CPU sets the carry flag:

     xor %eax, %eax
loop:
     ; loop body

     add $1, %eax
     jnc loop

Calculate floor value without FPU/SSE instruction

Presented algorithm works properly for any normalized floating point value, examples are given for double precision numbers (64-bit). Read more ...

Convert float to int without FPU/SSE

This short note shows how normalized floating point value could be safely converted to integer value without assistance of FPU/SSE. Only basic bit and arithmetic operations are used. Read more ...

fopen a directory

It's not clear how function fopen applied to a directory should behave, manual pages don't say anything about this. So, our common sense fail --- at least when use standard library shipped with GCC, beacuse fopen returns a valid handle.

Discussion on stackoverflow pointed that fseek or ftell would fail. But on my system it's not true, ftell(f, 0, SEEK_END) returns size of opened directory.

Only when we trying to read data using fread or fgetc the errno variable is set to EISDIR error code.

Here is output from simple test program:

$ ./a.out ~
testing '/home/wojtek'...
fopen: Success [errno=0]
fseek: Success [errno=0]
fseek result: 0
ftell: Success [errno=0]
ftell result: 24576
feof: Success [errno=0]
feof result: 0 (EOF=no)
fgetc: Is a directory [errno=21]
fgetc result: -1 (EOF=yes)
fread: Is a directory [errno=21]
fread result: 0