如何提高查找速度

mq110

原帖由 "mik" 发表：



如果，确定数组较大的。那么可以按 6 bytes 查、8 bytes

甚至更多。。。

这样是否更快。

我想不是这样的... 32位机来说 按4bytes 应该是最快的. 个人理解.如不对请指教.

mik

原帖由 "mq110" 发表：


我想不是这样的... 32位机来说 按4bytes 应该是最快的. 个人理解.如不对请指教.

但是，按 8 bytes 来查，明明是比 4 bytes 省了一半的时间嘛。

而且，在 gcc 中，编译器缺省对齐是 16 bytes 上。

1. andl $-16, esp

复制代码

雨丝风片

[quote]原帖由 "mik"]但是，按 8 bytes 来查，明明是比 4 bytes 省了一半的时间嘛。 [/quote 发表：


你在32位的机器上去判断一个64位的区域是否为空，请问你是如何
“比 4 bytes 省了一半的时间嘛”？ :wink:

mq110

同时处理32位2进制数. 怎么会8bytes 比4bytes 节省一半时间???不解.

mik

原帖由 "雨丝风片" 发表：


你在32位的机器上去判断一个64位的区域是否为空，请问你是如何
“比 4 bytes 省了一半的时间嘛”？ :wink:

嘿~~~

int main()
{
     int a[] = { 0, 1};
     int *p = a;

     if (*(long long*)p)
        printf("long long size is %d,%d\n"  a[1]);

     *(long long*)p = 0;
    if (!*(long long*)p)
        printf("long long size is %d,%d\n" a[1]);

    return 0;

}


你们试一试，结果如何？？？　

mq110

这能说明效率问题?

mik

[quote]原帖由 "mq110"]这能说明效率问题?[/quote 发表：

1. int main()
   
2. {
   
3.       int a[] = { 0, 1 };
   
4.       int *p = a;
   
5. 
   
6.      *p = 0;
   
7.      *(p+1) = 0;
   
8.   
   
9.      if ( !*p && !*(p+1))
   
10.          printf("%d\n",a[1]);
    
11. }

复制代码

gcc 3.3.1 编译为：

1.         leal        -8(%ebp), %eax
   
2.         movl        %eax, -12(%ebp)
   
3.         movl        -12(%ebp), %eax
   
4.         movl        $0, (%eax)
   
5.         movl        -12(%ebp), %eax
   
6.         addl        $4, %eax
   
7.         movl        $0, (%eax)
   
8.         movl        -12(%ebp), %eax
   
9.         cmpl        $0, (%eax)
   
10.         jne        .L2
    
11.         movl        -12(%ebp), %eax
    
12.         addl        $4, %eax
    
13.         cmpl        $0, (%eax)
    
14.         jne        .L2
    
15.         movl        -4(%ebp), %eax
    
16.         movl        %eax, 4(%esp)
    
17.         movl        $.LC0, (%esp)
    
18.         call        printf
    
19. .L2:
    
20.         movl        $0, %eax
    
21.         leave

复制代码

而：

1. int main()
   
2. {
   
3.     int a[] = { 0, 1};
   
4.     int *p = a;
   
5. 
   
6.      *(long long*)p = 0;
   
7.    if (!*(long long*)p)
   
8.        printf("long long size is %d,%d\n" a[1]);
   
9. 
   
10.    return 0;
    
11. }

复制代码

gcc 3.3.1编译为：

1.         leal        -8(%ebp), %eax
   
2.         movl        %eax, -12(%ebp)
   
3.         movl        -12(%ebp), %eax
   
4.         movl        $0, (%eax)
   
5.         movl        $0, 4(%eax)
   
6.         movl        -12(%ebp), %eax
   
7.         cmpl        $0, (%eax)
   
8.         jne        .L2
   
9.         movl        -4(%ebp), %eax
   
10.         movl        %eax, 4(%esp)
    
11.         movl        $.LC0, (%esp)
    
12.         call        printf
    
13. .L2:
    
14.         movl        $0, %eax
    
15.         leave

复制代码

用事实说话，不用解释了，对比一下：）

不过是未在优化编译的。　不知优化编译后，是否一样。。。

mik

将两段代码用优化　-O　编译了。

产生代码是差不多。

：）

win_hate

原帖由 "mik" 发表：


用事实说话，不用解释了，对比一下：）

不过是未在优化编译的。　不知优化编译后，是否一样。。。

1. int main()
   
2. {
   
3.    int a[] = { 0, 1};
   
4.    int *p = a;
   
5. 
   
6.     *(long long*)p = 0;
   
7.   if (!*(long long*)p)
   
8.       printf("long long size is %d,%d\n" a[1]);
   
9. 
   
10.   return 0;
    
11. }

复制代码

这段汇编是 gcc 生成的吗？

1. 
   
2.    leal   -8(%ebp), %eax            
   
3.    movl   %eax, -12(%ebp)          # p = a
   
4.    movl   -12(%ebp), %eax         
   
5.    movl   $0, (%eax)
   
6.    movl   $0, 4(%eax)              # *(long long *)p = 0
   
7.    movl   -12(%ebp), %eax          # eax <-- p, or a
   
8.    cmpl   $0, (%eax)               # a[0] == 0   ??? where is a[1]
   
9.    jne   .L2
   
10.    movl   -4(%ebp), %eax
    
11.    movl   %eax, 4(%esp)
    
12.    movl   $.LC0, (%esp)
    
13.    call   printf
    
14. .L2:
    
15.    movl   $0, %eax
    
16.    leave

复制代码

win_hate

同样的c代码(虽然没看明白你在干什么)，gcc 3.3.5 生成：

1. main:
   
2.         pushl   %ebp
   
3.         movl    %esp, %ebp
   
4.         subl    $24, %esp
   
5.         andl    $-16, %esp
   
6.         movl    $0, %eax
   
7.         subl    %eax, %esp
   
8.         movl    $0, -8(%ebp)
   
9.         movl    $1, -4(%ebp)
   
10.         leal    -8(%ebp), %eax
    
11.         movl    %eax, -12(%ebp)
    
12.         movl    -12(%ebp), %edx
    
13.         movl    (%edx), %eax             # eax <-- a
    
14.         orl     4(%edx), %eax            # eax <-- a[0] | a[1]
    
15.         testl   %eax, %eax
    
16.         jne     .L2
    
17.         movl    -4(%ebp), %eax
    
18.         movl    %eax, 4(%esp)
    
19.         movl    $.LC0, (%esp)
    
20.         call    printf
    
21. .L2:
    
22.         movl    $0, %eax
    
23.         leave
    
24.         ret
    

复制代码

a[1] 和 a[2] 都处理了。

关键是如何处理这个逻辑表达式

1. (!*(long long*)p)

复制代码

!a 应该把 a 转换为 int 还是......

不清楚标准上是怎么写的。

ps>; 我好象又记起了一些东西

如果 typeof(a) 是 long long, 那么 !a 被转换为 !(a==0)， long long 与long long 的比较。所以不处理 a[1] 的代码是错误的。