Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit33feb55

Browse files
committed
Replace bitwise looping with bytewise looping in hemdistsign and
sizebitvec of tsearch2, as well as identical code in several othercontrib modules. This provided about a 20X speedup in building alarge tsearch2 index ... didn't try to measure its effects for otheroperations. Thanks to Stephan Vollmer for providing a test case.
1 parent138fdf3 commit33feb55

File tree

8 files changed

+100
-82
lines changed

8 files changed

+100
-82
lines changed

‎contrib/intarray/_int.h

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -68,11 +68,6 @@ typedef char *BITVECP;
6868
a;\
6969
}
7070

71-
#defineLOOPBIT(a) \
72-
for(i=0;i<SIGLENBIT;i++) {\
73-
a;\
74-
}
75-
7671
/* beware of multiple evaluation of arguments to these macros! */
7772
#defineGETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
7873
#defineGETBITBYTE(x,i) ( (*((char*)(x)) >> (i)) & 0x01 )

‎contrib/intarray/_intbig_gist.c

Lines changed: 24 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -20,16 +20,25 @@ Datumg_intbig_picksplit(PG_FUNCTION_ARGS);
2020
Datumg_intbig_union(PG_FUNCTION_ARGS);
2121
Datumg_intbig_same(PG_FUNCTION_ARGS);
2222

23-
#defineSUMBIT(val) (\
24-
GETBITBYTE((val),0) + \
25-
GETBITBYTE((val),1) + \
26-
GETBITBYTE((val),2) + \
27-
GETBITBYTE((val),3) + \
28-
GETBITBYTE((val),4) + \
29-
GETBITBYTE((val),5) + \
30-
GETBITBYTE((val),6) + \
31-
GETBITBYTE((val),7) \
32-
)
23+
/* Number of one-bits in an unsigned byte */
24+
staticconstuint8number_of_ones[256]= {
25+
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
26+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
27+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
28+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
29+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
30+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
31+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
32+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
33+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
34+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
35+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
36+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
37+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
38+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
39+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
40+
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
41+
};
3342

3443
PG_FUNCTION_INFO_V1(_intbig_in);
3544
Datum_intbig_in(PG_FUNCTION_ARGS);
@@ -205,8 +214,7 @@ sizebitvec(BITVECP sign)
205214
i;
206215

207216
LOOPBYTE(
208-
size+=SUMBIT(sign);
209-
sign= (BITVECP) (((char*)sign)+1);
217+
size+=number_of_ones[(unsignedchar)sign[i]];
210218
);
211219
returnsize;
212220
}
@@ -215,11 +223,12 @@ static int
215223
hemdistsign(BITVECPa,BITVECPb)
216224
{
217225
inti,
226+
diff,
218227
dist=0;
219228

220-
LOOPBIT(
221-
if (GETBIT(a,i)!=GETBIT(b,i))
222-
dist++;
229+
LOOPBYTE(
230+
diff= (unsignedchar) (a[i] ^b[i]);
231+
dist+=number_of_ones[diff];
223232
);
224233
returndist;
225234
}

‎contrib/ltree/_ltree_gist.c

Lines changed: 27 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -30,18 +30,30 @@ Datum_ltree_consistent(PG_FUNCTION_ARGS);
3030

3131
#defineGETENTRY(vec,pos) ((ltree_gist *) DatumGetPointer((vec)->vector[(pos)].key))
3232
#defineNEXTVAL(x) ( (ltree*)( (char*)(x) + INTALIGN( VARSIZE(x) ) ) )
33-
#defineSUMBIT(val) ( \
34-
GETBITBYTE(val,0) + \
35-
GETBITBYTE(val,1) + \
36-
GETBITBYTE(val,2) + \
37-
GETBITBYTE(val,3) + \
38-
GETBITBYTE(val,4) + \
39-
GETBITBYTE(val,5) + \
40-
GETBITBYTE(val,6) + \
41-
GETBITBYTE(val,7)\
42-
)
33+
34+
/* Number of one-bits in an unsigned byte */
35+
staticconstuint8number_of_ones[256]= {
36+
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
37+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
38+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
39+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
40+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
41+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
42+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
43+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
44+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
45+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
46+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
47+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
48+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
49+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
50+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
51+
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
52+
};
53+
4354
#defineWISH_F(a,b,c) (double)( -(double)(((a)-(b))*((a)-(b))*((a)-(b)))*(c) )
4455

56+
4557
staticvoid
4658
hashing(BITVECPsign,ltree*t)
4759
{
@@ -207,8 +219,7 @@ sizebitvec(BITVECP sign)
207219
i;
208220

209221
ALOOPBYTE(
210-
size+=SUMBIT(*(char*)sign);
211-
sign= (BITVECP) (((char*)sign)+1);
222+
size+=number_of_ones[(unsignedchar)sign[i]];
212223
);
213224
returnsize;
214225
}
@@ -217,11 +228,12 @@ static int
217228
hemdistsign(BITVECPa,BITVECPb)
218229
{
219230
inti,
231+
diff,
220232
dist=0;
221233

222-
ALOOPBIT(
223-
if (GETBIT(a,i)!=GETBIT(b,i))
224-
dist++;
234+
ALOOPBYTE(
235+
diff= (unsignedchar) (a[i] ^b[i]);
236+
dist+=number_of_ones[diff];
225237
);
226238
returndist;
227239
}

‎contrib/ltree/ltree.h

Lines changed: 0 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -177,10 +177,6 @@ typedef unsigned char *BITVECP;
177177
for(i=0;i<SIGLEN;i++) {\
178178
a;\
179179
}
180-
#defineLOOPBIT(a) \
181-
for(i=0;i<SIGLENBIT;i++) {\
182-
a;\
183-
}
184180

185181
#defineGETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
186182
#defineGETBITBYTE(x,i) ( ((unsigned char)(x)) >> i & 0x01 )
@@ -238,10 +234,6 @@ typedef unsigned char ABITVEC[ASIGLEN];
238234
for(i=0;i<ASIGLEN;i++) {\
239235
a;\
240236
}
241-
#defineALOOPBIT(a) \
242-
for(i=0;i<ASIGLENBIT;i++) {\
243-
a;\
244-
}
245237

246238
#defineAHASHVAL(val) (((unsigned int)(val)) % ASIGLENBIT)
247239
#defineAHASH(sign,val) SETBIT((sign), AHASHVAL(val))

‎contrib/pg_trgm/trgm.h

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -55,11 +55,6 @@ typedef char *BITVECP;
5555
a;\
5656
}
5757

58-
#defineLOOPBIT(a) \
59-
for(i=0;i<SIGLENBIT;i++) {\
60-
a;\
61-
}
62-
6358
#defineGETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITBYTE ) ) )
6459
#defineGETBITBYTE(x,i) ( ((char)(x)) >> i & 0x01 )
6560
#defineCLRBIT(x,i) GETBYTE(x,i) &= ~( 0x01 << ( (i) % BITBYTE ) )

‎contrib/pg_trgm/trgm_gist.c

Lines changed: 24 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -36,16 +36,25 @@ Datumgtrgm_picksplit(PG_FUNCTION_ARGS);
3636

3737
#defineGETENTRY(vec,pos) ((TRGM *) DatumGetPointer((vec)->vector[(pos)].key))
3838

39-
#defineSUMBIT(val) ( \
40-
GETBITBYTE(val,0) + \
41-
GETBITBYTE(val,1) + \
42-
GETBITBYTE(val,2) + \
43-
GETBITBYTE(val,3) + \
44-
GETBITBYTE(val,4) + \
45-
GETBITBYTE(val,5) + \
46-
GETBITBYTE(val,6) + \
47-
GETBITBYTE(val,7)\
48-
)
39+
/* Number of one-bits in an unsigned byte */
40+
staticconstuint8number_of_ones[256]= {
41+
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
42+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
43+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
44+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
45+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
46+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
47+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
48+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
49+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
50+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
51+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
52+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
53+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
54+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
55+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
56+
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
57+
};
4958

5059

5160
Datum
@@ -298,8 +307,7 @@ sizebitvec(BITVECP sign)
298307
i;
299308

300309
LOOPBYTE(
301-
size+=SUMBIT(*(char*)sign);
302-
sign= (BITVECP) (((char*)sign)+1);
310+
size+=number_of_ones[(unsignedchar)sign[i]];
303311
);
304312
returnsize;
305313
}
@@ -308,11 +316,12 @@ static int
308316
hemdistsign(BITVECPa,BITVECPb)
309317
{
310318
inti,
319+
diff,
311320
dist=0;
312321

313-
LOOPBIT(
314-
if (GETBIT(a,i)!=GETBIT(b,i))
315-
dist++;
322+
LOOPBYTE(
323+
diff= (unsignedchar) (a[i] ^b[i]);
324+
dist+=number_of_ones[diff];
316325
);
317326
returndist;
318327
}

‎contrib/tsearch2/gistidx.c

Lines changed: 25 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -42,16 +42,26 @@ PG_FUNCTION_INFO_V1(gtsvector_picksplit);
4242
Datumgtsvector_picksplit(PG_FUNCTION_ARGS);
4343

4444
#defineGETENTRY(vec,pos) ((GISTTYPE *) DatumGetPointer((vec)->vector[(pos)].key))
45-
#defineSUMBIT(val) ( \
46-
GETBITBYTE(val,0) + \
47-
GETBITBYTE(val,1) + \
48-
GETBITBYTE(val,2) + \
49-
GETBITBYTE(val,3) + \
50-
GETBITBYTE(val,4) + \
51-
GETBITBYTE(val,5) + \
52-
GETBITBYTE(val,6) + \
53-
GETBITBYTE(val,7)\
54-
)
45+
46+
/* Number of one-bits in an unsigned byte */
47+
staticconstuint8number_of_ones[256]= {
48+
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
49+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
50+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
51+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
52+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
53+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
54+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
55+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
56+
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
57+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
58+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
59+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
60+
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
61+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
62+
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
63+
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
64+
};
5565

5666
staticint4sizebitvec(BITVECPsign);
5767

@@ -435,8 +445,7 @@ sizebitvec(BITVECP sign)
435445
i;
436446

437447
LOOPBYTE(
438-
size+=SUMBIT(*(char*)sign);
439-
sign= (BITVECP) (((char*)sign)+1);
448+
size+=number_of_ones[(unsignedchar)sign[i]];
440449
);
441450
returnsize;
442451
}
@@ -445,11 +454,12 @@ static int
445454
hemdistsign(BITVECPa,BITVECPb)
446455
{
447456
inti,
457+
diff,
448458
dist=0;
449459

450-
LOOPBIT(
451-
if (GETBIT(a,i)!=GETBIT(b,i))
452-
dist++;
460+
LOOPBYTE(
461+
diff= (unsignedchar) (a[i] ^b[i]);
462+
dist+=number_of_ones[diff];
453463
);
454464
returndist;
455465
}

‎contrib/tsearch2/gistidx.h

Lines changed: 0 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -21,10 +21,6 @@ typedef char *BITVECP;
2121
for(i=0;i<SIGLEN;i++) {\
2222
a;\
2323
}
24-
#defineLOOPBIT(a) \
25-
for(i=0;i<SIGLENBIT;i++) {\
26-
a;\
27-
}
2824

2925
#defineGETBYTE(x,i) ( *( (BITVECP)(x) + (int)( (i) / BITS_PER_BYTE ) ) )
3026
#defineGETBITBYTE(x,i) ( ((char)(x)) >> (i) & 0x01 )

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp