
平台论坛博客文库

论坛徽章:: 44

31楼 [报告]

发表于 2016-11-03 13:54 |只看该作者

回复 30# yulihua49

怎么可能，你看我的代码不就用的是数组么……

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

yulihua49

巨富豪门

论坛徽章:: 15

32楼 [报告]

发表于 2016-11-03 14:33 |只看该作者

本帖最后由 yulihua49 于 2016-11-03 14:59 编辑

windoze 发表于 2016-11-03 13:54
回复 30# yulihua49

怎么可能，你看我的代码不就用的是数组么……

我查不到。

-O3是STL快了。大概是宏，更容易优化吧。
优化的汇编码看了，完全看不懂，二者都被打乱了函数调用的次序。比较函数都被嵌入到代码里了。
又试了下使用库函数，这个完全不能与应用代码揉合，就得老老实实调函数。速度更慢了。但是看汇编码，简单明了，已经无法优化了。

-O3对宏的优化水平的确超过了一般汇编程序员的能力。

附上汇编码，还看得出来就是前边的cpp程序吗？

[sdbc@erg0devprc01 test]$ cat stl_test.s
.file "stl_test.cpp"
.text
.p2align 4,,15
.globl _Z3cmpPvS_i
.type _Z3cmpPvS_i, @function
_Z3cmpPvS_i:
.LFB1218:
.cfi_startproc
movslq %edx, %rdx
movl (%rsi,%rdx,4), %eax
subl (%rdi), %eax
ret
.cfi_endproc
.LFE1218:
.size _Z3cmpPvS_i, .-_Z3cmpPvS_i
.p2align 4,,15
.globl _Z5test2v
.type _Z5test2v, @function
_Z5test2v:
.LFB1221:
.cfi_startproc
movl $100000, %edi
movl $test_data, %esi
.L3:
movq %rdi, %rax
sarq %rax
leaq (%rsi,%rax,4), %rcx
cmpl $8000, (%rcx)
jg .L7
jmp .L11
.p2align 4,,10
.p2align 3
.L5:
movq %rax, %rdx
sarq %rdx
leaq (%rsi,%rdx,4), %rcx
cmpl $8000, (%rcx)
jle .L4
movq %rdx, %rax
.L7:
testq %rax, %rax
jg .L5
.L6:
subq $test_data, %rsi
sarq $2, %rsi
subq $1, %rsi
movq %rsi, garbage(%rip)
ret
.L11:
movq %rax, %rdx
movq %rdi, %rax
.p2align 4,,10
.p2align 3
.L4:
subq %rdx, %rax
leaq 4(%rcx), %rsi
leaq -1(%rax), %rdi
testq %rdi, %rdi
jg .L3
jmp .L6
.cfi_endproc
.LFE1221:
.size _Z5test2v, .-_Z5test2v
.p2align 4,,15
.globl _Z5test1v
.type _Z5test1v, @function
_Z5test1v:
.LFB1219:
.cfi_startproc
subq $24, %rsp
.cfi_def_cfa_offset 32
movl $_Z3cmpPvS_i, %ecx
movl $100000, %edx
movq %rsp, %rdi
movl $test_data, %esi
movl $8000, (%rsp)
call upperBound
subl $1, %eax
cltq
movq %rax, garbage(%rip)
addq $24, %rsp
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE1219:
.size _Z5test1v, .-_Z5test1v
.section .text.unlikely,"ax",@progbits
.type _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc.part.1, @function
_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc.part.1:
.LFB1242:
.cfi_startproc
pushq %rax
.cfi_def_cfa_offset 16
movq (%rdi), %rax
addq -24(%rax), %rdi
movl 32(%rdi), %esi
orl $1, %esi
call _ZNSt9basic_iosIcSt11char_traitsIcEE5clearESt12_Ios_Iostate
popq %rdx
.cfi_def_cfa_offset 8
ret
.cfi_endproc
.LFE1242:
.size _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc.part.1, .-_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc.part.1
.text
.p2align 4,,15
.globl _Z18generate_test_datav
.type _Z18generate_test_datav, @function
_Z18generate_test_datav:
.LFB1217:
.cfi_startproc
xorl %ecx, %ecx
movabsq $-3689348814741910323, %rsi
.p2align 4,,10
.p2align 3
.L18:
movq %rcx, %rax
mulq %rsi
shrq $3, %rdx
movl %edx, test_data(,%rcx,4)
addq $1, %rcx
cmpq $100000, %rcx
jne .L18
rep ret
.cfi_endproc
.LFE1217:
.size _Z18generate_test_datav, .-_Z18generate_test_datav
.section .rodata.str1.1,"aMS",@progbits,1
.LC0:
.string "Duration: "
.LC1:
.string ",N="
.text
.p2align 4,,15
.globl _Z7time_itmPFvvE
.type _Z7time_itmPFvvE, @function
_Z7time_itmPFvvE:
.LFB1222:
.cfi_startproc
pushq %r13
.cfi_def_cfa_offset 16
.cfi_offset 13, -16
pushq %r12
.cfi_def_cfa_offset 24
.cfi_offset 12, -24
movq %rsi, %r12
pushq %rbp
.cfi_def_cfa_offset 32
.cfi_offset 6, -32
movq %rdi, %rbp
pushq %rbx
.cfi_def_cfa_offset 40
.cfi_offset 3, -40
xorl %ebx, %ebx
subq $8, %rsp
.cfi_def_cfa_offset 48
call now_usec
testq %rbp, %rbp
movq %rax, %r13
je .L23
.p2align 4,,10
.p2align 3
.L27:
addq $1, %rbx
call *%r12
cmpq %rbp, %rbx
jne .L27
.L23:
movq garbage(%rip), %rbp
call now_usec
movl $10, %edx
movq %rax, %rbx
movl $.LC0, %esi
movl $_ZSt4cout, %edi
call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
movl %ebx, %esi
movl $_ZSt4cout, %edi
subl %r13d, %esi
call _ZNSolsEi
movl $3, %edx
movq %rax, %rbx
movl $.LC1, %esi
movq %rax, %rdi
call _ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
movq %rbp, %rsi
movq %rbx, %rdi
call _ZNSo9_M_insertImEERSoT_
movq %rax, %rbp
movq (%rax), %rax
movq -24(%rax), %rax
movq 240(%rbp,%rax), %rbx
testq %rbx, %rbx
je .L30
cmpb $0, 56(%rbx)
je .L25
movzbl 67(%rbx), %eax
.L26:
movq %rbp, %rdi
movsbl %al, %esi
call _ZNSo3putEc
addq $8, %rsp
.cfi_remember_state
.cfi_def_cfa_offset 40
movq %rax, %rdi
popq %rbx
.cfi_def_cfa_offset 32
popq %rbp
.cfi_def_cfa_offset 24
popq %r12
.cfi_def_cfa_offset 16
popq %r13
.cfi_def_cfa_offset 8
jmp _ZNSo5flushEv
.p2align 4,,10
.p2align 3
.L25:
.cfi_restore_state
movq %rbx, %rdi
call _ZNKSt5ctypeIcE13_M_widen_initEv
movq (%rbx), %rax
movl $10, %esi
movq %rbx, %rdi
call *48(%rax)
jmp .L26
.L30:
call _ZSt16__throw_bad_castv
.cfi_endproc
.LFE1222:
.size _Z7time_itmPFvvE, .-_Z7time_itmPFvvE
.section .rodata.str1.1
.LC2:
.string "Binary "
.LC3:
.string "MAP "
.section .text.startup,"ax",@progbits
.p2align 4,,15
.globl main
.type main, @function
main:
.LFB1223:
.cfi_startproc
xorl %ecx, %ecx
movabsq $-3689348814741910323, %rsi
.p2align 4,,10
.p2align 3
.L33:
movq %rcx, %rax
mulq %rsi
shrq $3, %rdx
movl %edx, test_data(,%rcx,4)
addq $1, %rcx
cmpq $100000, %rcx
jne .L33
pushq %rbx
.cfi_def_cfa_offset 16
.cfi_offset 3, -16
movl $100, %ebx
subq $16, %rsp
.cfi_def_cfa_offset 32
.p2align 4,,10
.p2align 3
.L40:
movl $test_data, %esi
movq %rsp, %rdi
movl $_Z3cmpPvS_i, %ecx
movl $100000, %edx
movl $8000, (%rsp)
call upperBound
movl $test_data, %esi
movl $100000, %edi
.L34:
movq %rdi, %rax
sarq %rax
leaq (%rsi,%rax,4), %rcx
cmpl $8000, (%rcx)
jg .L38
jmp .L44
.p2align 4,,10
.p2align 3
.L36:
movq %rax, %rdx
sarq %rdx
leaq (%rsi,%rdx,4), %rcx
cmpl $8000, (%rcx)
jle .L35
movq %rdx, %rax
.L38:
testq %rax, %rax
jg .L36
.L37:
subq $test_data, %rsi
sarq $2, %rsi
subq $1, %rsi
subq $1, %rbx
movq %rsi, garbage(%rip)
jne .L40
movl $.LC2, %esi
movl $_ZSt4cout, %edi
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
movl $_Z5test1v, %esi
movl $100000, %edi
call _Z7time_itmPFvvE
movl $.LC3, %esi
movl $_ZSt4cout, %edi
call _ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
movl $_Z5test2v, %esi
movl $100000, %edi
call _Z7time_itmPFvvE
addq $16, %rsp
.cfi_remember_state
.cfi_def_cfa_offset 16
xorl %eax, %eax
popq %rbx
.cfi_restore 3
.cfi_def_cfa_offset 8
ret
.L44:
.cfi_restore_state
movq %rax, %rdx
movq %rdi, %rax
.p2align 4,,10
.p2align 3
.L35:
subq %rdx, %rax
leaq 4(%rcx), %rsi
leaq -1(%rax), %rdi
testq %rdi, %rdi
jg .L34
jmp .L37
.cfi_endproc
.LFE1223:
.size main, .-main
.p2align 4,,15
.type _GLOBAL__sub_I_test_data, @function
_GLOBAL__sub_I_test_data:
.LFB1240:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
movl $_ZStL8__ioinit, %edi
call _ZNSt8ios_base4InitC1Ev
movl $__dso_handle, %edx
movl $_ZStL8__ioinit, %esi
movl $_ZNSt8ios_base4InitD1Ev, %edi
addq $8, %rsp
.cfi_def_cfa_offset 8
jmp __cxa_atexit
.cfi_endproc
.LFE1240:
.size _GLOBAL__sub_I_test_data, .-_GLOBAL__sub_I_test_data
.section .init_array,"aw"
.align 8
.quad _GLOBAL__sub_I_test_data
.globl garbage
.bss
.align 16
.type garbage, @object
.size garbage, 8
garbage:
.zero 8
.globl test_data
.align 32
.type test_data, @object
.size test_data, 400000
test_data:
.zero 400000
.local _ZStL8__ioinit
.comm _ZStL8__ioinit,1,1
.hidden __dso_handle
.ident "GCC: (GNU) 4.8.3 20140911 (Red Hat 4.8.3-9)"
.section .note.GNU-stack,"",@progbits
[sdbc@erg0devprc01 test]$

复制代码

yulihua49

巨富豪门

论坛徽章:: 15

33楼 [报告]

发表于 2016-11-03 15:01 |只看该作者

windoze 发表于 2016-11-03 13:54
回复 30# yulihua49

怎么可能，你看我的代码不就用的是数组么……

这组函数的使用说明你能给我直接贴出来吗？

windoze

版主

论坛徽章:: 44

34楼 [报告]

发表于 2016-11-03 22:41 |只看该作者

本帖最后由 windoze 于 2016-11-03 22:45 编辑

回复 33# yulihua49

std::upper_bound的说明在这里：
http://en.cppreference.com/w/cpp/algorithm/upper_bound

简要的说一下，这个函数有两个重载：

template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

复制代码

第一个用std::less，第二个允许自定义compare。
[first, last)这个前闭后开区间定义了一个序列，这个函数会在这个序列里找到第一个比value大的元素，也就是满足comp(value, element)==true的元素。对于数组x[size]，你可以用x和x+size。
这个函数用二分法查找，所以序列要求是由小到大排好序的。
Compare要求是可传递且不可逆的，对于任意abc，如果comp(a,b)==true且comp(b,c)==true，则comp(a,c)必须是true；
如果comp(a,b)==true，则comp(b,a)必须是false。
简单说就是Compare定义了一个partial order且对于每一次comp(x,y)调用都要保证a和b可比较。

因为这个函数是个template，所以很多东西在开了优化以后都会inline，而且在我的测试程序中comp是一个functor，所以也会inline，这样就会比较快了。

yulihua49

巨富豪门

论坛徽章:: 15

35楼 [报告]

发表于 2016-11-04 13:10 |只看该作者

本帖最后由 yulihua49 于 2016-11-04 13:44 编辑

windoze 发表于 2016-11-03 22:41
回复 33# yulihua49

std::upper_bound的说明在这里：

C++真的很神奇，服了。

这是我修改下，再做的测试。
其中Binary是调的库函数，完全不能inline。STL是inline的：
./stl_test
Binary Duration: 14619,N=79999
STL Duration: 5397,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 7352,N=79999
STL Duration: 12376,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 7420,N=79999
STL Duration: 5348,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 7638,N=79999
STL Duration: 19317,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 14582,N=79999
STL Duration: 5287,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 14591,N=79999
STL Duration: 5422,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 7420,N=79999
STL Duration: 12317,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 18667,N=79999
STL Duration: 5370,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 14392,N=79999
STL Duration: 5316,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 18378,N=79999
STL Duration: 5242,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 7375,N=79999
STL Duration: 5507,N=79999
[sdbc@erg0devprc01 test]$ ./stl_test
Binary Duration: 7531,N=79999
STL Duration: 12426,N=79999

在库函数里不知道数据类型，所以要在比较函数里要自己取下标数据，这个开销也很显著。STL因为知道数据类型，直接用寄存器进行数组寻址。
如果针对复杂数据结构数组，多字段组合KEY，估计它优势没那么高。
这是stl的汇编码：

cat stl_a.s
.file "stl_a.cpp"
.text
.p2align 4,,15
.globl _Z5test2Pimi
.type _Z5test2Pimi, @function
_Z5test2Pimi:
.LFB410:
.cfi_startproc
salq $2, %rsi
movq %rdi, %r9
sarq $2, %rsi
.L2:
testq %rsi, %rsi
jle .L5
movq %rsi, %rax
sarq %rax
leaq (%rdi,%rax,4), %r8
cmpl (%r8), %edx
jl .L6
jmp .L10
.p2align 4,,10
.p2align 3
.L4:
movq %rax, %rcx
sarq %rcx
leaq (%rdi,%rcx,4), %r8
cmpl %edx, (%r8)
jle .L3
movq %rcx, %rax
.L6:
testq %rax, %rax
jne .L4
.L5:
subq %r9, %rdi
sarq $2, %rdi
leal -1(%rdi), %eax
ret
.L10:
movq %rax, %rcx
movq %rsi, %rax
.p2align 4,,10
.p2align 3
.L3:
subq %rcx, %rax
leaq 4(%r8), %rdi
leaq -1(%rax), %rsi
jmp .L2
.cfi_endproc
.LFE410:
.size _Z5test2Pimi, .-_Z5test2Pimi
.ident "GCC: (GNU) 4.8.3 20140911 (Red Hat 4.8.3-9)"
.section .note.GNU-stack,"",@progbits

复制代码

upper_bound是宏，根本没有作为一个函数出现。
一套复杂的下标计算和取数据操作，它一条指令解决了：
leaq (%rdi,%rcx,4), %r8

test1的汇编码，无法优化了：

.globl _Z5test1Pimi
.type _Z5test1Pimi, @function
_Z5test1Pimi:
.LFB1219:
.cfi_startproc
subq $24, %rsp
.cfi_def_cfa_offset 32
movl $_Z3cmpPvS_i, %ecx
movl %edx, 12(%rsp)
movl %esi, %edx
movq %rdi, %rsi
leaq 12(%rsp), %rdi
call upperBound
addq $24, %rsp
.cfi_def_cfa_offset 8
subl $1, %eax
ret
.cfi_endproc
.LFE1219:
.size _Z5test1Pimi, .-_Z5test1Pimi

复制代码

yulihua49

巨富豪门

论坛徽章:: 15

36楼 [报告]

发表于 2016-11-04 14:07 |只看该作者

yulihua49 发表于 2016-11-04 13:10
C++真的很神奇，服了。

这是我修改下，再做的测试。

/**
* @brief Finds the last position in which @p __val could be inserted
* without changing the ordering.
* @ingroup binary_search_algorithms
* @param __first An iterator.
* @param __last Another iterator.
* @param __val The search term.
* @return An iterator pointing to the first element greater than @p __val,
* or end() if no elements are greater than @p __val.
* @ingroup binary_search_algorithms
*/
template<typename _ForwardIterator, typename _Tp>
_ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
__glibcxx_requires_partitioned_upper(__first, __last, __val);
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__val < *__middle)
__len = __half;
else
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}
/**
* @brief Finds the last position in which @p __val could be inserted
* without changing the ordering.
* @ingroup binary_search_algorithms
* @param __first An iterator.
* @param __last Another iterator.
* @param __val The search term.
* @param __comp A functor to use for comparisons.
* @return An iterator pointing to the first element greater than @p __val,
* or end() if no elements are greater than @p __val.
* @ingroup binary_search_algorithms
*
* The comparison function should have the same effects on ordering as
* the function used for the initial sort.
*/
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator
upper_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_Tp, _ValueType>)
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__comp(__val, *__middle))
__len = __half;
else
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
}
return __first;
}

复制代码

找到了STL的源码，很神奇。

mr_sev

稍有积蓄

论坛徽章:: 3

37楼 [报告]

发表于 2016-11-04 17:31 |只看该作者

回复 21# yulihua49
像你那样的情况，我直接用红黑树了。

https://github.com/dongwencai/kernel_rbtree/blob/master/demo.c

mr_sev

稍有积蓄

论坛徽章:: 3

38楼 [报告]

发表于 2016-11-04 17:35 |只看该作者

https://github.com/dongwencai/kernel_rbtree/blob/master/rbtree.c

cokeboL

巨富豪门

论坛徽章:: 36

39楼 [报告]

发表于 2016-11-04 21:15 |只看该作者

C++是未来高级智慧生命——机器人的基础，人类终将退出历史舞台被机器人取代

lol

windoze

版主

论坛徽章:: 44

40楼 [报告]

发表于 2016-11-04 21:44 |只看该作者

本帖最后由 windoze 于 2016-11-04 21:47 编辑

回复 35# yulihua49

和C不同，C++是强类型语言，永远都知道数据的类型和尺寸，所以编译器永远都可以把下标或者结构体成员的访问直接优化成偏移量。

我一直建议用惯了C的人就把C++当做一个优化更好的C来用，什么虚函数继承多态之类OO相关的东西放在一边，只用C和template部分，这样心情好效率也高。基本算法STL里有一大堆： http://en.cppreference.com/w/cpp/header/algorithm ，都是些很常用而且自己写很容易出错的东西；容器也有一堆现成的，虽说list和map之类的东西可能效率略差，但是array和vector确实比原生数组方便多了。
等STL里的东西用熟了之后你就可以动手写自己的算法和容器了，像是KM/BMP或者B+Tree之类，写对了的话也比C快不少。

string和iostream一般在追求效率的地方应该尽量避免，这一块确实坑很多，不过说实话，关掉sync之后，iostream也比printf快。

唯一需要注意的地方就是所有template函数都要放在头文件里，编译时间也慢了很多。

另外C粉可以关注一下Rust，虽说这货现在坑依然不少，但是真的很有意思。

评分

参与人数 1	信誉积分 +10	收起理由
lxyscls	+ 10	赞一个!

查看全部评分

1 2 345 6 7 / 7 页下一页

返回列表

Chinaunix › 论坛 › 程序设计 › C/C++ › 通用可重复值的排序数组的二分法检索

[C] 通用可重复值的排序数组的二分法检索 [复制链接]

评分