I’ve been wondering how much of the data we keep in memory is actually useful, as opposed to being bits which are mostly or entirely constant.\u00a0 Recently I hacked up a Valgrind tool to get some initial measurements.<\/p>\n
Imagine a machine instruction that does a 32-bit memory read.\u00a0 If the read value is observed only ever to be one of a small set, let’s say, 1, 2 or 3, then we might suspect that most of the bits in the word are unused.\u00a0 Should we be concerned?\u00a0 It depends whether the instruction accesses a wide range of addresses: if it does, that might be a clue that we’ve got some inefficient representation going on over a large area of memory.<\/p>\n
MVP puts this into practice.\u00a0 It watches all 1, 2, 4 and 8 byte non-stack memory read instructions, observing both the spread of read values and the spread of accessed addresses.\u00a0 For each monitored instruction, it computes an aggregate wastefulness score.\u00a0 This is the the number of always-constant bits in the values multiplied by (some approximation of) the number of different accessed addresses.<\/p>\n
You can level various kinds of “Bogus!” accusations at it, but it does give some indication of structure and array fields that are not working very hard.\u00a0 For example, given this:<\/p>\n
it will tell you that the “sum += a[i]” reads are mostly pulling in constant bits:<\/p>\n 31 out of the 32 bits read are constant (it has some sophistication about ignoring constant sign bits), and the accesses are spread over 31,251 different “sectors” (128-byte chunks of address space).\u00a0 Hence this read instruction gets a relatively high wastefulness metric of 968,781.<\/p>\n MVP runs Firefox without difficulty.\u00a0 Results are interesting.\u00a0 A couple of high-roller tidbits:<\/p>\n fast_composite_src_x888_0565 converts image data from 24 bit 8:8:8 format to 16-bit 5:6:5 format, and the 24 bit values are parked in 32 bit words.\u00a0 The data is spread widely (142,913 sectors) and the top 8 bits of the read data are observed to be constant, as we’d expect.<\/p>\n This has to do with<\/p>\n 16 constant bits out of 16 implies that tc->topStmt->type (a uint16) has only ever been observed to be STMT_BLOCK here.<\/p>\n The most striking observation from the initial numbers, though, is somewhat obvious: that on a 64 bit platform, pointer-intensive structures are space-inefficient.\u00a0 There are large numbers of 64-bit load instructions that pull in values with 36 or so constant bits.\u00a0 That would correspond to fetching addresses of objects scattered across a few hundred megabytes of address space.<\/p>\n Perhaps we should work to minimise the number of heap objects.\u00a0 Maybe what we need is a way to detect object pairs with coupled lifetimes, so they can be merged into a single object, and the connecting pointers removed.<\/p>\n Anyway, enough speculation.\u00a0 The tool is very much WIP.\u00a0 If anybody is interested in trying it out, or has comments\/suggestions, let me know.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" I’ve been wondering how much of the data we keep in memory is actually useful, as opposed to being bits which are mostly or entirely constant.\u00a0 Recently I hacked up a Valgrind tool to get some initial measurements. Imagine a … Continue reading<\/a><\/p>\n","protected":false},"author":240,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts\/112"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/users\/240"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/comments?post=112"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/posts\/112\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/media?parent=112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/categories?post=112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/jseward\/wp-json\/wp\/v2\/tags?post=112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}} #define MILLION 1000000
\nint a[MILLION];<\/code><\/p>\n for (i = 0; i < MILLION; i++)\u00a0\u00a0 a[i] = (i & 1) ? 1 : -1;<\/code><\/p>\n <\/code><\/p>\n \/\/ ... later ...
\nfor (i = 0; i < MILLION; i++)\u00a0\u00a0 sum += a[i];<\/code><\/p>\n wasted 968,781\u00a0 (31\/32 cbs, 31,251 sects)\u00a0 0x40057E: main (mvp1.c:25)<\/pre>\n
wasted 1,143,304\u00a0 (8\/32 cbs, 142,913 sects)\r\n 0x6431A7B: fast_composite_src_x888_0565 (pixman-fast-path.c:904)<\/pre>\n
wasted 989,696\u00a0 (16\/16 cbs, 61,856 sects)\u00a0\r\n 0x652B054: js::NameNode::create(JSAtom*, JSTreeContext*)\r\n \u00a0 (jsparse.cpp:798)<\/pre>\n
pn_dflags = (!tc->topStmt || tc->topStmt->type == STMT_BLOCK)\r\n ? PND_BLOCKCHILD : 0;<\/pre>\n