关于一个运算优化的问题

liangbch

使用了更多的汇编。函数logSum几乎 完全汇编（没有使用386以上的指令）化了，这样终于达到了传说中的0.062. 以下代码为主函数。

1. int main(int argc, char* argv[])
2. {
3. int i,count;
4. DWORD d0,d1,d2,d3, nlogSum;
5. UINT128 *pData=NULL;
7. scanf("%d",&count);
8. pData=new UINT128[count];
10. for (i=0;i<count;i++)
11. {
12. scanf("%u %u %u %u",&d0,&d1,&d2,&d3);
13. pData[i].U[0]=d0;
14. pData[i].U[1]=d1;
15. pData[i].U[2]=d2;
16. pData[i].U[3]=d3;
17. }
19. qsort( (void *)pData, (size_t)count, sizeof(UINT128), Uint128Compare );
20. nlogSum= logSum(pData,count);
21. delete[] pData; pData=NULL;
23. printf("%lu\n",nlogSum);
24. return 0;
25. }

复制代码

无心人

这么多汇编，可就有点麻烦了 呵呵

gxqcn

1. for (i=0;i<count;i++)
2. {
3. scanf("%u %u %u %u",&d0,&d1,&d2,&d3);
4. pData[i].U[0]=d0;
5. pData[i].U[1]=d1;
6. pData[i].U[2]=d2;
7. pData[i].U[3]=d3;
8. }

复制代码

也可简化成以下形式吧？

1. for (i=0;i<count;i++)
2. {
3. scanf("%u %u %u %u",&(pData[i].U[0]),&(pData[i].U[1]),&(pData[i].U[2]),&(pData[i].U[3]));
4. }

复制代码

gxqcn

祝贺各位！ 正如 litaoye 在 151# 所言：

原帖由 litaoye 于 2009-3-20 04:05 发表 。。。这道题的平均水平都被大家带高了！

无心人

这其中似乎有别的因素在影响时间 比如L2 Cache等

liangbch

完全可以呀，不过对性能几乎没有影响。

无心人

2. #include <stdlib.h>
3. #include <stdio.h>
4. #include <string.h>
6. typedef struct
7. {
8. unsigned int d[4];
9. } UINT128;
11. unsigned int CompTable[128][2] = {0,0, 0,0, 0,0, 0,1, 1,0, 1,0, 1,1, 2,0, 2,0, 2,1, 3,0, 3,0, 3,0, 3,1,
12. 4,0,4,0,4,1,5,0,5,0,5,1,6,0,6,0,6,0,6,1,7,0,7,0,7,1,8,0,8,0,
13. 8,1,9,0,9,0,9,0,9,1,10,0,10,0,10,1,11,0,11,0,11,1,12,0,12,
14. 0,12,0,12,1,13,0,13,0,13,1,14,0,14,0,14,1,15,0,15,0,15,0,15,
15. 1,16,0,16,0,16,1,17,0,17,0,17,1,18,0,18,0,18,0,18,1,19,0,19,
16. 0,19,1,20,0,20,0,20,1,21,0,21,0,21,0,21,1,22,0,22,0,22,1,23,
17. 0,23,0,23,1,24,0,24,0,24,0,24,1,25,0,25,0,25,1,26,0,26,0,26,
18. 1,27,0,27,0,27,0,27,1,28,0,28,0,28,1,29,0,29,0,29,1,30,0,30,
19. 0,30,1,31,0,31,0,31,0,31,1,32,0,32,0,32,1,33,0,33,0,33,1,34,
20. 0,34,0,34,0,34,1,35,0,35,0,35,1,36,0,36,0,36,1,37,0,37,0,37,0,37,1,38,0};
22. UINT128 pow10[40] = {1,0,0,0,
23. 10,0,0,0,
24. 100,0,0,0,
25. 1000,0,0,0,
26. 10000,0,0,0,
27. 100000,0,0,0,
28. 1000000,0,0,0,
29. 10000000,0,0,0,
30. 100000000,0,0,0,
31. 1000000000,0,0,0,
32. 1410065408,2,0,0,
33. 1215752192,23,0,0,
34. 3567587328,232,0,0,
35. 1316134912,2328,0,0,
36. 276447232,23283,0,0,
37. 2764472320,232830,0,0,
38. 1874919424,2328306,0,0,
39. 1569325056,23283064,0,0,
40. 2808348672,232830643,0,0,
41. 2313682944,2328306436,0,0,
42. 1661992960,1808227885,5,0,
43. 3735027712,902409669,54,0,
44. 2990538752,434162106,542,0,
45. 4135583744,46653770,5421,0,
46. 2701131776,466537709,54210,0,
47. 1241513984,370409800,542101,0,
48. 3825205248,3704098002,5421010,0,
49. 3892314112,2681241660,54210108,0,
50. 268435456,1042612833,542101086,0,
51. 2684354560,1836193738,1126043566,1,
52. 1073741824,1182068202,2670501072,12,
53. 2147483648,3230747430,935206946,126,
54. 0,2242703233,762134875,1262,
55. 0,952195850,3326381459,12621,
56. 0,932023908,3199043520,126217,
57. 0,730304488,1925664130,1262177,
58. 0,3008077584,2076772117,12621774,
59. 0,16004768,3587851993,126217744,
60. 0,160047680,1518781562,1262177448,
61. 0, 0, 0, 0};
63. /*
64. __declspec(naked)
65. int __fastcall log2(UINT128 * n)
66. {
67. __asm
68. {
69. bsr eax, [ecx]
70. bsr edx, [ecx + 4]
71. add edx, 32
72. cmp [ecx + 4], 0
73. cmovne eax, edx
74. bsr edx, [ecx + 8]
75. add edx, 64
76. cmp [ecx + 8], 0
77. cmovne eax, edx
78. bsr edx, [ecx + 12]
79. add edx, 96
80. cmp [ecx + 12], 0
81. cmovne eax, edx
82. ret
83. }
84. }
86. */
87. int compare( const void * a, const void * b )
88. {
89. unsigned int * l, * r;
90. l = (unsigned int *)a; r = (unsigned int *)b;
91. if (*(l+3) != *(r + 3)) return (*(l + 3) > *(r+3) ? 1 : -1);
92. if (*(l+2) != *(r + 2)) return (*(l + 2) > *(r+2) ? 1 : -1);
93. if (*(l+1) != *(r + 1)) return (*(l + 1) > *(r+1) ? 1 : -1);
94. return (* l > * r ? 1 : (* l == * r ? 0 : -1));
95. }
97. __declspec(naked)
98. int __fastcall log_10(UINT128 * n)
99. {
100. __asm
101. {
102. bsr edx, [ecx]
103. bsr eax, [ecx + 4]
104. add eax, 32
105. cmp dword ptr [ecx + 4], 0
106. cmovne edx, eax
107. bsr eax, [ecx + 8]
108. add eax, 64
109. cmp dword ptr [ecx + 8], 0
110. cmovne edx, eax
111. bsr eax, [ecx + 12]
112. add eax, 96
113. cmp dword ptr [ecx + 12], 0
114. cmovne edx, eax
115. mov eax, dword ptr CompTable[8 * edx]
116. cmp dword ptr CompTable[8 * edx + 4], 0
117. je ex
118. add eax, 1
119. mov edx, eax
120. shl edx, 4
121. push ebx
122. mov ebx, [ecx]
123. sub ebx, pow10[edx]
124. mov ebx, [ecx + 4]
125. sbb ebx, pow10[edx + 4]
126. mov ebx, [ecx + 8]
127. sbb ebx, pow10[edx + 8]
128. mov ebx, [ecx + 12]
129. sbb ebx, pow10[edx + 12]
130. sbb ebx, ebx
131. add eax, ebx
132. pop ebx
133. ex:
134. ret
135. }
136. }
138. __declspec(naked)
139. int __fastcall logxor(UINT128 * a, UINT128 * b)
140. {
141. __asm
142. {
143. mov eax, 0
144. ret
145. }
146. }
148. int main(int argc, char* argv[])
149. {
150. int count,result,i,j, k;
151. UINT128 data[5000], r;
153. scanf("%d",&count);
154. result=0;
155. i = 0;
156. while (i < count) {
157. scanf("%u", &data[i].d[3]);
158. scanf("%u", &data[i].d[2]);
159. scanf("%u", &data[i].d[1]);
160. scanf("%u", &data[i].d[0]);
161. i++;
162. }
164. qsort( (void *)data, (size_t)count, 16, compare );
166. for (i= 0; i < count - 1; i ++)
167. {
168. for (j = i + 1; j < count; j ++)
169. {
171. r.d[3] = data[i].d[3] ^ data[j].d[3];
172. r.d[2] = data[i].d[2] ^ data[j].d[2];
173. r.d[1] = data[i].d[1] ^ data[j].d[1];
174. r.d[0] = data[i].d[0] ^ data[j].d[0];
175. // printf("%u, %u, %u, %u", r.d[3], r.d[2], r.d[1], r.d[0]);
176. // printf(":%u\n", log_10(&r));
177. result += log_10(&r);
178. }
179. }
181. printf("%u",result*2);
182. return 0;
183. }

复制代码

0.156 和各位还存在一点点差距

无心人

有点昏昏的 好像，大概，似乎，寄存器不够用了啊 不知道 宝宝怎么设定的寄存器

liangbch

我的建议，如果先求128bit的xor运算再求 log10 就比较慢。我是将2者结合在一起的。在我的程序中，先对两个128bit数的最高32bit的边求xor，如果值为0，继续求下32bit。 直到结果非0。 如果前64bit是0，那么在和10^n比较的时候就只需比较后64bit 就可以了。 我的xorLog10函数没有内存写指令，也不用SSE,SSE2,MMX 和 REP cmpd 等指令，寄存器完全够用了。

无心人

俺用了xmm寄存器了 所以也够用了 就是汇编语句有点长 快100行了 所以毛病太多了 使劲调试中