NotificationsYou must be signed in to change notification settings
Fork6
Star31

Commitab5b4e2

committed

Speed up AllocSetFreeIndex, which is a significant cost in palloc and pfree,

by using a lookup table instead of a naive shift-and-count loop. Based oncode originally posted by Sean Eron Anderson athttp://graphics.stanford.edu/%7eseander/bithacks.html.Greg Stark did the research and benchmarking to show that this is whatwe should use. Jeremy Kerr first noticed that this is a hotspot thatcould be optimized, though we ended up not using his suggestion ofplatform-specific bit-searching code.

1 parentf3f45c8 commitab5b4e2Copy full SHA for ab5b4e2

File tree

1 file changed

+32

-9

lines changed

src/backend/utils/mmgr
- aset.c

1 file changed

+32

-9

lines changed

`‎src/backend/utils/mmgr/aset.c‎`

Lines changed: 32 additions & 9 deletions

Original file line number	Diff line number	Diff line change
`@@ -11,7 +11,7 @@`
`11`	`11`	`* Portions Copyright (c) 1994, Regents of the University of California`
`12`	`12`	`*`
`13`	`13`	`* IDENTIFICATION`
`14`		`- * $PostgreSQL: pgsql/src/backend/utils/mmgr/aset.c,v 1.79 2009/06/11 14:49:06 momjian Exp $`
	`14`	`+ * $PostgreSQL: pgsql/src/backend/utils/mmgr/aset.c,v 1.80 2009/07/21 19:53:12 tgl Exp $`
`15`	`15`	`*`
`16`	`16`	`* NOTE:`
`17`	`17`	`*This is a new (Feb. 05, 1999) implementation of the allocation set`
`@@ -238,6 +238,17 @@ static MemoryContextMethods AllocSetMethods = {`
`238`	`238`	`#endif`
`239`	`239`	`};`
`240`	`240`
	`241`	`+/*`
	`242`	`+ * Table for AllocSetFreeIndex`
	`243`	`+ */`
	`244`	`+#defineLT16(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n`
	`245`	`+`
	`246`	`+staticconstunsignedcharLogTable256[256]=`
	`247`	`+{`
	`248`	`+0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,`
	`249`	`+LT16(5),LT16(6),LT16(6),LT16(7),LT16(7),LT16(7),LT16(7),`
	`250`	`+LT16(8),LT16(8),LT16(8),LT16(8),LT16(8),LT16(8),LT16(8),LT16(8)`
	`251`	`+};`
`241`	`252`
`242`	`253`	`/* ----------`
`243`	`254`	`* Debug macros`
`@@ -266,18 +277,30 @@ static MemoryContextMethods AllocSetMethods = {`
`266`	`277`	`staticinlineint`
`267`	`278`	`AllocSetFreeIndex(Sizesize)`
`268`	`279`	`{`
`269`		`-intidx=0;`
	`280`	`+intidx;`
	`281`	`+unsignedintt,`
	`282`	`+tsize;`
`270`	`283`
`271`		`-if (size>0)`
	`284`	`+if (size>(1 <<ALLOC_MINBITS))`
`272`	`285`	`{`
`273`		`-size= (size-1) >>ALLOC_MINBITS;`
`274`		`-while (size!=0)`
`275`		`-{`
`276`		`-idx++;`
`277`		`-size >>=1;`
`278`		`-}`
	`286`	`+tsize= (size-1) >>ALLOC_MINBITS;`
	`287`	`+`
	`288`	`+/*`
	`289`	`+ * At this point we need to obtain log2(tsize)+1, ie, the number`
	`290`	`+ * of not-all-zero bits at the right. We used to do this with a`
	`291`	`+ * shift-and-count loop, but this function is enough of a hotspot`
	`292`	`+ * to justify micro-optimization effort. The best approach seems`
	`293`	`+ * to be to use a lookup table. Note that this code assumes that`
	`294`	`+ * ALLOCSET_NUM_FREELISTS <= 17, since we only cope with two bytes`
	`295`	`+ * of the tsize value.`
	`296`	`+ */`
	`297`	`+t=tsize >>8;`
	`298`	`+idx=t ?LogTable256[t]+8 :LogTable256[tsize];`
	`299`	`+`
`279`	`300`	`Assert(idx<ALLOCSET_NUM_FREELISTS);`
`280`	`301`	`}`
	`302`	`+else`
	`303`	`+idx=0;`
`281`	`304`
`282`	`305`	`returnidx;`
`283`	`306`	`}`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

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

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commitab5b4e2

File tree

1 file changed

1 file changed

`‎src/backend/utils/mmgr/aset.c‎`

0 commit comments