Ускорение Python в 150 раз с использованием C

Си-код тормозит почти в 10 раз - можно ведь считать параллельно (по диагонали):

levenshtein sse_variant len
103535 113 12863 113 125 uint16
440665 221 41669 221 250
1670380 445 151093 445 500
6740058 896 967752 896 1000
28449713 1769 2670073 1769 2000 7.5 vs 0.7ms
112313687 3517 9621706 3517 4000 29.5 vs 2.5ms
417518031 7034 40077041 7034 8000
1709693702 14038 166281964 14038 16000
6812783553 28117 730058352 28117 32000 uint16
... ... ... ... ... ... ...
103583 113 7589 149 125 uint8

Вариант с длиной в uint8 применим только если коротка строка короче 128 символов - иначе будет переполнение. Железо Intel(R) Core(TM) i7-2600K CPU @ 3.80GHz время при желании можно пересчитать из тактов.

Ключи сборки gcc -O3 -mavx -msse4 test.cpp -o test && ./test , если применить avx2/avx512 можно наверно ещё 2-4 раза ускорить (-mavx погоды особой не делает - у него для целых нужных команд нет).

Оптимизированный код (короткая строка должна быть короче 32К символов):

#define sseLen 16
#define sseNum 8
typedef uint16_t sseType;
typedef sseType sseReg __attribute__ ((vector_size (sseLen),aligned(1)));
static int sse_variant(const char* _s1, const char* _s2) {
    int n1 = strlen(_s1), n2 = strlen(_s2);
	if(n1>n2) return sse_variant(_s2,_s1);
	if(!n1) return n2;
    sseType* a = (sseType*)malloc((n1+2*sseNum) * sizeof(*a));
    sseType* b = (sseType*)malloc((n1+2*sseNum) * sizeof(*b));
    sseType* c = (sseType*)malloc((n1+2*sseNum) * sizeof(*c));
	sseType* s1 = (sseType*)malloc((n1+2*sseNum)*sizeof(*s1));
	sseType* s2 = (sseType*)malloc((n2+2*sseNum)*sizeof(*s2));
    if (!a || !b || !c || !s1 || !s2) { 
		free(a); free(b); free(c); free(s1); free(s2); return -1; 
	}
	for(int i=0;i<n1;++i) s1[n1-1-i]=_s1[i];
	for(int i=0;i<n2;++i) s2[i]=_s2[i];
	b[0]=a[0]=a[1]=0;
	for(int n=1;n<n1+n2;++n){
		sseType *d=c; c=b; b=a; a=d;
		int nn=n<n1?n:(n<n2?n1:n1+n2-n);
		int o=0;
		if(n<n1) a[o++]=0;
		int i1=n1-(n<n1?n:n1);
		int i2=n>n1?n-n1:0;
#if 1
		const sseReg one={1,1,1,1,1,1,1,1};
		for(int i=0,j=n>n1;i<nn;i+=sseNum,o+=sseNum){
			sseReg v1=*(sseReg*)(s1+i1); i1+=sseNum;
			sseReg v2=*(sseReg*)(s2+i2); i2+=sseNum;
			sseReg t1=*(sseReg*)(c+j)+one-(v1==v2); j+=sseNum;
			v1=*(sseReg*)(b+i); 
			v2=*(sseReg*)(b+i+1);
			sseReg t2=v1>v2?v1:v2;
			*(sseReg*)(a+o)=t1>t2?t1:t2; 
		}
#else		
		for(int i=0,j=n>n1;i<nn;++i,++o){
			int t1=(s1[i1++]!=s2[i2++]?1:2)+c[j++];
			int t2=b[i]>b[i+1]?b[i]:b[i+1];
			a[o]=t1>t2?t1:t2;
		}
#endif		
		if(n<n2) a[nn+(n<n1)]=0;
	}
	int ans=n1+n2-a[0];
	free(a); free(b); free(c); free(s1); free(s2); 
	return ans;
}