非常慢的char*访问

Question

EDIT: SOLUTION

不用查找表，我可以对值进行分组，这样我就可以使用一系列条件来选择值。

原来的3.702663s现在变成了1.630996。

更进一步，在switch语句中使用range，性能提高了3.759549 ->1.013868s(改进3.7倍)

不清楚为什么查找表会导致延迟，但希望我能弄清楚，因为我更喜欢表。

---

也许我已经看了太多次，或者我忽略了一些非常愚蠢的东西，但无论我改变什么，我都会遇到同样的问题。问题是访问buffer应该是常数时间，但是如果我使用变量third而不是first作为table中的索引，则处理文件所需的时间几乎是2倍。任何大小的文件都可以。

(test.txt可以通过填充一个字节文件来创建<= 0x40)

为1GB文件计时。

$ gcc -O2 -o test test.c && ./test && rm test
2.0287s
3.7871s

任何想法?

(我写这个是为了演示这个问题，是的，除此之外就没有用了)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static const uint8_t table[64] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};
#define RUN(variable)                                                          
idx = 0;                                                                   
first = buffer[idx];                                                       
second = buffer[idx];                                                      
next = idx + table[second];                                                
third = buffer[next];                                                      
start = clock();                                                           
while (idx < length) {                                                     
first = second;                                                        
second = third;                                                        
idx = next;                                                            
next += table[variable];                                               
third = (next < length) ? (buffer[next]) : 0;                          
}                                                                          
end = clock();                                                             
printf("%fsn", (float)(end - start) / CLOCKS_PER_SEC);
int main() {
uint8_t first, second, third;
size_t idx, next, length;
clock_t start, end;
FILE* file = fopen("test.txt", "rb");
fseek(file, 0, SEEK_END);
length = ftell(file);
rewind(file);
char* buffer;
buffer = (char*)malloc(sizeof(char) * length);
fread(buffer, 1, length, file);
fclose(file);
RUN(first);
RUN(third);
free(buffer);
return 0;
}

编辑:没有宏，单独的开始/结束

gcc -O2 -o test test.c && ./test && rm test
1.9776s
3.6817s

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static const uint8_t table[64] = {
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};
int main() {
uint8_t first, second, third;
size_t idx, next, result, length;
clock_t start1, end1, start2, end2;
FILE* file = fopen("test.txt", "rb");
fseek(file, 0, SEEK_END);
length = ftell(file);
rewind(file);
char* buffer;
buffer = (char*)malloc(sizeof(char) * length);
fread(buffer, 1, length, file);
fclose(file);
// Using variable 'first' and {start,end}1
idx = 0;
first = buffer[idx];
second = buffer[idx];
next = idx + table[second];
third = buffer[next];
start1 = clock();
while (idx < length) {
first = second;
second = third;
idx = next;
next += table[first];
third = (next < length) ? (buffer[next]) : 0;
}
end1 = clock();
printf("%fsn", (float)(end1 - start1) / CLOCKS_PER_SEC);
// Using variable 'third' and {start,end}2
idx = 0;
first = buffer[idx];
second = buffer[idx];
next = idx + table[second];
third = buffer[next];
start2 = clock();
while (idx < length) {
first = second;
second = third;
idx = next;
next += table[third];
third = (next < length) ? (buffer[next]) : 0;
}
end2 = clock();
printf("%fsn", (float)(end2 - start2) / CLOCKS_PER_SEC);

free(buffer);
return 0;
}

Answer 1

行内:

third = (next < length) ? (buffer[next]) : 0;
//       1 < 64 ? 64 : 0;

在您的示例中，在第一次传递时，third = 64将在下一个循环中转到表数组的外部:

next += table[third]; // table[64]