I spotted some low-hanging fruit in the pglz compression routine. It
uses a hash table to keep track of string prefixes it has seen:
#define PGLZ_HISTORY_LISTS 8192 /* must be power of 2 */
#define PGLZ_HISTORY_SIZE 4096
/* ----------
* Statically allocated work arrays for history
* ----------
*/
static PGLZ_HistEntry *hist_start[PGLZ_HISTORY_LISTS];
static PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE];
The hist_start array has to be zeroed at every invocation of
pglz_compress(). That's relatively expensive, when compressing small
values; on a 64-bit machine, 8192 * 8 = 64 kB.
The pointers in hist_start point to entries in hist_entries. If we
replace the pointers with int16 indexes into hist_entries, we can shrink
hist_start array to 8192 * 2 = 16 kB.
Also, in PGLZ_HistEntry:
typedef struct PGLZ_HistEntry
{
struct PGLZ_HistEntry *next; /* links for my hash key's list */
struct PGLZ_HistEntry *prev;
int hindex; /* my current hash key
*/
const char *pos; /* my input position */
} PGLZ_HistEntry;
we can replace next and prev with indexes into the hist_entries array,
halving the size of that struct, and thus the hist_entries array from
32*4096=128kB to 64kB. I'm not sure how significant that is -
hist_entries array doesn't need to be zeroed out like hist_start does -
but it might buy us something in CPU cache efficiency.
I ran some performance tests with this:
testname | unpatched | patched
-------------------+-----------+---------
5k text | 1.55933 | 1.57337
512b random | 6.70911 | 5.41420
100k of same byte | 1.92319 | 1.94880
2k random | 4.29494 | 3.88782
100k random | 1.10400 | 1.07982
512b text | 9.26736 | 7.55828
(6 rows)
The datum used in the "5k text" test was the first 5k from the
"doc/src/sgml/func.sgml" file in the source tree, and "512b text" was
the first 512 bytes from the same file. The data in the random tests was
completely random, and in the "100k of same byte" test, a single byte
was repeated 100000 times (ie. compresses really well).
Each test inserts rows into a temporary table. The table has 10 bytea
columns, and the same value is inserted in every column. The number of
rows inserted was scaled so that each test inserts roughly 500 MB of
data. Each test was repeated 20 times, and the values listed above are
the minimum runtimes in seconds.
I spotted this while looking at Amit's WAL update delta encoding patch.
My earlier suggestion to just use the pglz compressor for the delta
encoding didn't work too well because the pglz compressor was too
expensive, especially for small values. This patch might help with that..
In summary, this seems like a pretty clear win for short values, and a
wash for long values. Not surprising, as this greatly lowers the startup
cost of pglz_compress(). We're past feature freeze, but how would people
feel about committing this?
- Heikki
--
- Heikki
diff --git a/src/backend/utils/adt/pg_lzcompress.c b/src/backend/utils/adt/pg_lzcompress.c
index 66c64c1..b4a8b8b 100644
--- a/src/backend/utils/adt/pg_lzcompress.c
+++ b/src/backend/utils/adt/pg_lzcompress.c
@@ -198,9 +198,9 @@
*/
typedef struct PGLZ_HistEntry
{
- struct PGLZ_HistEntry *next; /* links for my hash key's list */
- struct PGLZ_HistEntry *prev;
- int hindex; /* my current hash key */
+ int16 next; /* links for my hash key's list */
+ int16 prev;
+ uint32 hindex; /* my current hash key */
const char *pos; /* my input position */
} PGLZ_HistEntry;
@@ -241,9 +241,11 @@ const PGLZ_Strategy *const PGLZ_strategy_always = &strategy_always_data;
* Statically allocated work arrays for history
* ----------
*/
-static PGLZ_HistEntry *hist_start[PGLZ_HISTORY_LISTS];
-static PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE];
+static int16 hist_start[PGLZ_HISTORY_LISTS];
+static PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE + 1];
+/* Element 0 in hist_entries is unused, and means 'invalid'. */
+#define INVALID_ENTRY 0
/* ----------
* pglz_hist_idx -
@@ -279,25 +281,25 @@ static PGLZ_HistEntry hist_entries[PGLZ_HISTORY_SIZE];
#define pglz_hist_add(_hs,_he,_hn,_recycle,_s,_e) \
do { \
int __hindex = pglz_hist_idx((_s),(_e)); \
- PGLZ_HistEntry **__myhsp = &(_hs)[__hindex]; \
+ int16 *__myhsp = &(_hs)[__hindex]; \
PGLZ_HistEntry *__myhe = &(_he)[_hn]; \
if (_recycle) { \
- if (__myhe->prev == NULL) \
+ if (__myhe->prev == INVALID_ENTRY) \
(_hs)[__myhe->hindex] = __myhe->next; \
else \
- __myhe->prev->next = __myhe->next; \
- if (__myhe->next != NULL) \
- __myhe->next->prev = __myhe->prev; \
+ (_he)[__myhe->prev].next = __myhe->next; \
+ if (__myhe->next != INVALID_ENTRY) \
+ (_he)[__myhe->next].prev = __myhe->prev; \
} \
__myhe->next = *__myhsp; \
- __myhe->prev = NULL; \
+ __myhe->prev = INVALID_ENTRY; \
__myhe->hindex = __hindex; \
__myhe->pos = (_s); \
- if (*__myhsp != NULL) \
- (*__myhsp)->prev = __myhe; \
- *__myhsp = __myhe; \
- if (++(_hn) >= PGLZ_HISTORY_SIZE) { \
- (_hn) = 0; \
+ if (*__myhsp != INVALID_ENTRY) \
+ (_he)[(*__myhsp)].prev = _hn; \
+ *__myhsp = _hn; \
+ if (++(_hn) >= PGLZ_HISTORY_SIZE + 1) { \
+ (_hn) = 1; \
(_recycle) = true; \
} \
} while (0)
@@ -372,19 +374,20 @@ do { \
* ----------
*/
static inline int
-pglz_find_match(PGLZ_HistEntry **hstart, const char *input, const char *end,
+pglz_find_match(int16 *hstart, const char *input, const char *end,
int *lenp, int *offp, int good_match, int good_drop)
{
- PGLZ_HistEntry *hent;
+ int16 hentno;
int32 len = 0;
int32 off = 0;
/*
* Traverse the linked history list until a good enough match is found.
*/
- hent = hstart[pglz_hist_idx(input, end)];
- while (hent)
+ hentno = hstart[pglz_hist_idx(input, end)];
+ while (hentno != INVALID_ENTRY)
{
+ PGLZ_HistEntry *hent = &hist_entries[hentno];
const char *ip = input;
const char *hp = hent->pos;
int32 thisoff;
@@ -443,13 +446,13 @@ pglz_find_match(PGLZ_HistEntry **hstart, const char *input, const char *end,
/*
* Advance to the next history entry
*/
- hent = hent->next;
+ hentno = hent->next;
/*
* Be happy with lesser good matches the more entries we visited. But
* no point in doing calculation if we're at end of list.
*/
- if (hent)
+ if (hentno != INVALID_ENTRY)
{
if (len >= good_match)
break;
@@ -484,7 +487,7 @@ pglz_compress(const char *source, int32 slen, PGLZ_Header *dest,
{
unsigned char *bp = ((unsigned char *) dest) + sizeof(PGLZ_Header);
unsigned char *bstart = bp;
- int hist_next = 0;
+ int hist_next = 1;
bool hist_recycle = false;
const char *dp = source;
const char *dend = source + slen;
drop table if exists testresults;
create table testresults (testname text, seconds numeric, tblsize bigint);
drop table if exists tmp;
create temporary table tmp (b1 bytea, b2 bytea, b3 bytea, b4 bytea, b5 bytea, b6 bytea, b7 bytea, b8 bytea, b9 bytea, b10 bytea);
do $$
declare
iterations int4 := 20;
i int4;
iter int4;
testname text;
data bytea;
nrows int4;
begintime numeric;
endtime numeric;
begin
for testname, data, nrows in select * from tests where enabled loop
raise notice 'running % iterations of test ''%''', iterations, testname;
for iter in 1..iterations loop
truncate tmp;
checkpoint;
begintime := extract(epoch from clock_timestamp());
for i in 1..nrows by 500 loop
insert into tmp select data, data, data, data, data, data, data, data, data, data from generate_series(1, 500);
end loop;
endtime := extract(epoch from clock_timestamp());
insert into testresults values (testname, endtime - begintime, pg_total_relation_size('tmp'));
end loop;
end loop;
end;
$$;
select * from testresults;
CREATE TABLE tests (
testname text,
data bytea,
nrows integer,
enabled boolean
);
COPY tests (testname, data, nrows, enabled) FROM stdin;
5k text \\x3c212d2d20646f632f7372632f73676d6c2f66756e632e73676d6c202d2d3e0a0a203c636861707465722069643d2266756e6374696f6e73223e0a20203c7469746c653e46756e6374696f6e7320616e64204f70657261746f72733c2f7469746c653e0a0a20203c696e6465787465726d207a6f6e653d2266756e6374696f6e73223e0a2020203c7072696d6172793e66756e6374696f6e3c2f7072696d6172793e0a20203c2f696e6465787465726d3e0a0a20203c696e6465787465726d207a6f6e653d2266756e6374696f6e73223e0a2020203c7072696d6172793e6f70657261746f723c2f7072696d6172793e0a20203c2f696e6465787465726d3e0a0a20203c706172613e0a2020203c70726f647563746e616d653e506f737467726553514c3c2f70726f647563746e616d653e2070726f76696465732061206c61726765206e756d626572206f660a20202066756e6374696f6e7320616e64206f70657261746f727320666f7220746865206275696c742d696e20646174612074797065732e202055736572732063616e20616c736f0a202020646566696e65207468656972206f776e2066756e6374696f6e7320616e64206f70657261746f72732c2061732064657363726962656420696e0a2020203c78726566206c696e6b656e643d227365727665722d70726f6772616d6d696e67223e2e20205468650a2020203c6170706c69636174696f6e3e7073716c3c2f6170706c69636174696f6e3e20636f6d6d616e6473203c636f6d6d616e643e5c64663c2f636f6d6d616e643e20616e640a2020203c636f6d6d616e643e5c646f3c2f636f6d6d616e643e2063616e206265207573656420746f206c69737420616c6c0a202020617661696c61626c652066756e6374696f6e7320616e64206f70657261746f72732c20726573706563746976656c792e0a20203c2f706172613e0a0a20203c706172613e0a202020496620796f752061726520636f6e6365726e65642061626f757420706f72746162696c697479207468656e206e6f74652074686174206d6f7374206f660a2020207468652066756e6374696f6e7320616e64206f70657261746f72732064657363726962656420696e207468697320636861707465722c2077697468207468650a202020657863657074696f6e206f6620746865206d6f7374207472697669616c2061726974686d6574696320616e6420636f6d70617269736f6e206f70657261746f72730a202020616e6420736f6d65206578706c696369746c79206d61726b65642066756e6374696f6e732c20617265206e6f7420737065636966696564206279207468650a2020203c6163726f6e796d3e53514c3c2f6163726f6e796d3e207374616e646172642e20536f6d65206f66207468697320657874656e6465642066756e6374696f6e616c6974790a20202069732070726573656e7420696e206f74686572203c6163726f6e796d3e53514c3c2f6163726f6e796d3e206461746162617365206d616e6167656d656e740a20202073797374656d732c20616e6420696e206d616e7920636173657320746869732066756e6374696f6e616c69747920697320636f6d70617469626c6520616e640a202020636f6e73697374656e74206265747765656e2074686520766172696f757320696d706c656d656e746174696f6e732e202054686973206368617074657220697320616c736f0a2020206e6f7420657868617573746976653b20206164646974696f6e616c2066756e6374696f6e732061707065617220696e2072656c6576616e742073656374696f6e73206f660a202020746865206d616e75616c2e0a20203c2f706172613e0a0a0a20203c73656374312069643d2266756e6374696f6e732d6c6f676963616c223e0a2020203c7469746c653e4c6f676963616c204f70657261746f72733c2f7469746c653e0a0a2020203c696e6465787465726d207a6f6e653d2266756e6374696f6e732d6c6f676963616c223e0a202020203c7072696d6172793e6f70657261746f723c2f7072696d6172793e0a202020203c7365636f6e646172793e6c6f676963616c3c2f7365636f6e646172793e0a2020203c2f696e6465787465726d3e0a0a2020203c696e6465787465726d3e0a202020203c7072696d6172793e426f6f6c65616e3c2f7072696d6172793e0a202020203c7365636f6e646172793e6f70657261746f72733c2f7365636f6e646172793e0a202020203c7365653e6f70657261746f72732c206c6f676963616c3c2f7365653e0a2020203c2f696e6465787465726d3e0a0a2020203c706172613e0a2020202054686520757375616c206c6f676963616c206f70657261746f72732061726520617661696c61626c653a0a0a202020203c696e6465787465726d3e0a20202020203c7072696d6172793e414e4420286f70657261746f72293c2f7072696d6172793e0a202020203c2f696e6465787465726d3e0a0a202020203c696e6465787465726d3e0a20202020203c7072696d6172793e4f5220286f70657261746f72293c2f7072696d6172793e0a202020203c2f696e6465787465726d3e0a0a202020203c696e6465787465726d3e0a20202020203c7072696d6172793e4e4f5420286f70657261746f72293c2f7072696d6172793e0a202020203c2f696e6465787465726d3e0a0a202020203c696e6465787465726d3e0a20202020203c7072696d6172793e636f6e6a756e6374696f6e3c2f7072696d6172793e0a202020203c2f696e6465787465726d3e0a0a202020203c696e6465787465726d3e0a20202020203c7072696d6172793e6469736a756e6374696f6e3c2f7072696d6172793e0a202020203c2f696e6465787465726d3e0a0a202020203c696e6465787465726d3e0a20202020203c7072696d6172793e6e65676174696f6e3c2f7072696d6172793e0a202020203c2f696e6465787465726d3e0a0a202020203c73696d706c656c6973743e0a20202020203c6d656d6265723e3c6c69746572616c3e414e443c2f3e3c2f6d656d6265723e0a20202020203c6d656d6265723e3c6c69746572616c3e4f523c2f3e3c2f6d656d6265723e0a20202020203c6d656d6265723e3c6c69746572616c3e4e4f543c2f3e3c2f6d656d6265723e0a202020203c2f73696d706c656c6973743e0a0a202020203c6163726f6e796d3e53514c3c2f6163726f6e796d3e207573657320612074687265652d76616c756564206c6f6769632073797374656d207769746820747275652c0a2020202066616c73652c20616e64203c6c69746572616c3e6e756c6c3c2f3e2c20776869636820726570726573656e7473203c71756f74653e756e6b6e6f776e3c2f71756f74653e2e0a202020204f6273657276652074686520666f6c6c6f77696e67207472757468207461626c65733a0a0a202020203c696e666f726d616c7461626c653e0a20202020203c7467726f757020636f6c733d2234223e0a2020202020203c74686561643e0a202020202020203c726f773e0a20202020202020203c656e7472793e3c7265706c61636561626c653e613c2f7265706c61636561626c653e3c2f656e7472793e0a20202020202020203c656e7472793e3c7265706c61636561626c653e623c2f7265706c61636561626c653e3c2f656e7472793e0a20202020202020203c656e7472793e3c7265706c61636561626c653e613c2f7265706c61636561626c653e20414e44203c7265706c61636561626c653e623c2f7265706c61636561626c653e3c2f656e7472793e0a20202020202020203c656e7472793e3c7265706c61636561626c653e613c2f7265706c61636561626c653e204f52203c7265706c61636561626c653e623c2f7265706c61636561626c653e3c2f656e7472793e0a202020202020203c2f726f773e0a2020202020203c2f74686561643e0a0a2020202020203c74626f64793e0a202020202020203c726f773e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a202020202020203c2f726f773e0a2020202020203c2f74626f64793e0a20202020203c2f7467726f75703e0a202020203c2f696e666f726d616c7461626c653e0a0a202020203c696e666f726d616c7461626c653e0a20202020203c7467726f757020636f6c733d2232223e0a2020202020203c74686561643e0a202020202020203c726f773e0a20202020202020203c656e7472793e3c7265706c61636561626c653e613c2f7265706c61636561626c653e3c2f656e7472793e0a20202020202020203c656e7472793e4e4f54203c7265706c61636561626c653e613c2f7265706c61636561626c653e3c2f656e7472793e0a202020202020203c2f726f773e0a2020202020203c2f74686561643e0a0a2020202020203c74626f64793e0a202020202020203c726f773e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e46414c53453c2f656e7472793e0a20202020202020203c656e7472793e545255453c2f656e7472793e0a202020202020203c2f726f773e0a0a202020202020203c726f773e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a20202020202020203c656e7472793e4e554c4c3c2f656e7472793e0a202020202020203c2f726f773e0a2020202020203c2f74626f64793e0a20202020203c2f7467726f75703e0a202020203c2f696e666f726d616c7461626c653e0a2020203c2f706172613e0a0a2020203c706172613e0a20202020546865206f70657261746f7273203c6c69746572616c3e414e443c2f6c69746572616c3e20616e64203c6c69746572616c3e4f523c2f6c69746572616c3e206172650a20202020636f6d6d757461746976652c20746861742069732c20796f752063616e2073776974636820746865206c65667420616e64207269676874206f706572616e640a20202020776974686f757420616666656374696e672074686520726573756c742e202042757420736565203c787265660a202020206c696e6b656e643d2273796e7461782d657870726573732d6576616c223e20666f72206d6f726520696e666f726d6174696f6e2061626f7574207468650a202020206f72646572206f66206576616c756174696f6e206f662073756265787072657373696f6e732e0a2020203c2f706172613e0a20203c2f73656374313e0a0a20203c73656374312069643d2266756e6374696f6e732d636f6d70617269736f6e223e0a2020203c7469746c653e436f6d70617269736f6e204f70657261746f72733c2f7469746c653e0a0a2020203c696e6465787465726d207a6f6e653d2266756e6374696f6e732d636f6d70617269736f6e223e0a202020203c7072696d6172793e636f6d70617269736f6e3c2f7072696d6172793e0a202020203c7365636f6e646172793e6f70657261746f72733c2f7365636f6e646172793e0a2020203c2f696e6465787465726d3e0a0a2020203c706172613e0a2020202054686520757375616c20636f6d70617269736f6e206f70657261746f72732061726520617661696c61626c652c2073686f776e20696e203c787265660a202020206c696e6b656e643d2266756e6374696f6e732d636f6d70617269736f6e2d7461626c65223e2e0a2020203c2f706172613e0a0a2020203c7461626c652069643d2266756e6374696f6e732d636f6d70617269736f6e2d7461626c65223e0a202020203c7469746c653e436f6d70617269736f6e204f70657261746f72733c2f7469746c653e0a202020203c7467726f757020636f6c733d2232223e0a20202020203c74686561643e0a2020202020203c726f773e0a20202020 25000 t
\.
insert into tests (testname, data, nrows, enabled)
select '512b text', substr(data, 0, 512), 100000, true from tests where testname = '5k text';
create temporary table randomhex (t text);
copy randomhex from program 'cat /dev/urandom | hexdump -e ''/1 "%02x"'' -n 102400 -v';
create temporary table randombytes (b bytea);
insert into randombytes select ('\x' || t)::bytea from randomhex;
insert into tests (testname, data, nrows, enabled)
select '2k random', substr(b, 0, 2048), 20000, true from randombytes;
insert into tests (testname, data, nrows, enabled)
select '100k random', substr(b, 0, 102400), 500, true from randombytes;
insert into tests (testname, data, nrows, enabled)
select '512b random', substr(b, 0, 512), 75000, true from randombytes;
insert into tests (testname, data, nrows, enabled)
select '100k of same byte', ('\x' || repeat('aa', 102400))::bytea, 35000, true;
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
