Speeding up searching in linked list

Sounds crazy, but it's possible in some cases. Here are experiments results - 3 times faster isn't so bad.

list                          :      0.780s, speedup  1.00
array list (4)                :      0.703s, speedup  1.11
array list (8)                :      0.515s, speedup  1.51
SIMD array list (4)           :      0.365s, speedup  2.14
SIMD array list (8)           :      0.258s, speedup  3.03

MSVC 2013 Release code

Today I had a quite long session with debugger and release code, you know: no debugger symbols and optimized code. I spotted two pieces of assembly that forced me to check if compilation mode was really set to release.

00000000000000D9  mov         byte ptr [rcx+1Fh],dl 
00000000000000DC  mov         byte ptr [rdx+rcx],0 
00000000000000E0  movzx       edx,byte ptr [rcx+1Fh] 
00000000000000E4  movzx       eax,dl 

First dl is stored in memory. It's ok. Then edx is used as an offset. Also ok. Seems that compiler knows that highest bits of edx are zeros i.e. edx = dl. Not so fast - edx is reloaded with it's original value and then eax is populated with the same value. These two movzx could be replaced with single mov eax, edx.

And another:

00000000000000BF  movaps      xmm6,xmmword ptr [foo] 
00000000000000C4  movdqa      xmmword ptr [foo],xmm6 

Yes, load & store the same value. Completely useless! Moreover, xmm6 isn't used in following code. (It's worth noting that load is done by an FP-unit and store by integer unit, inter-unit transfers cost one additional cycle on some processor.)

Above instruction sequences were produced by the newest compiler from Microsoft (MSVC 2013, update 3).

Fork bomb in Windows

It's really simple. Just install Cygwin, write fork bomb (even by accident) and finally run in bash - works fine. I had to restart my machine with restart button.

Intepolation search revisited

Interpolation search revisited -- theoretical complexity of interpolation search is very promising, but...

Conversion number to hexadecimal representation

Conversion numbers to hexadecimal representation - SWAR, plain SSE, and draft of BMI2 implementation.

Article SSSE3: printing hex values describes the same topic but is limited to exploit PSHUFB.

String literals are weird (at least in C/C++)

Simple quiz: what is the length of this string "\xbadcafe"?

1. 5 letters
2. 4 letters
3. 2 letters
4. 1 letter

The correct answer is d, i.e. single letter. In C/C++ escape sequence "\x..." consumes all hexadecimal digits.

Python: rename file in Windows

Observation: function os.remove under Windows doesn't allow to overwrite an existing file. Python from Cygwin works properly.

Here is a workaround:

def rename_file(old, new):
    if sys.platform != 'win32':
        os.rename(new, old)
    else:
        os.remove(old)
        os.rename(new, old)