{"id":1744,"date":"2018-01-06T14:57:40","date_gmt":"2018-01-06T04:57:40","guid":{"rendered":"http:\/\/brnz.org\/hbr\/?p=1744"},"modified":"2018-01-06T14:58:47","modified_gmt":"2018-01-06T04:58:47","slug":"a-little-bit-of-floating-point-in-a-memory-allocator-part-2-a-little-bit-of-floating-point","status":"publish","type":"post","link":"https:\/\/brnz.org\/hbr\/?p=1744","title":{"rendered":"A little bit of floating point in a memory allocator \u2014 Part 2: The floating point"},"content":{"rendered":"

[Previously]<\/a><\/p>\n

This post contains the same material as\u00a0this thread of tweets<\/a>, with a few minor edits.<\/p>\n

In IEEE754, floating point numbers are represented like this:<\/p>\n

\u00b12\u207f\u207f\u207f\u00d71.sss…<\/p>\n

nnn is the exponent, which is floor(log2(size))<\/span>\u00a0— which happens to be the fl<\/span> value computed by TLSF.<\/p>\n

sss… is the significand fraction: the part that follows the decimal point, which happens to be sl<\/span>.<\/p>\n

And so to calculate fl<\/span> and sl<\/span>, all we need to do is convert size<\/span> to a floating point value (on recent x86 hardware, that’s a single instruction). Then we can extract the exponent, and the upper bits of the fractional part, and we’re all done :D<\/p>\n

That can be implemented like this:<\/p>\n

\r\ndouble sf = (int64_t)size;\r\nuint64_t sfi;\r\nmemcpy(&sfi, &sf, 8);\r\nfl = (sfi >> 52) - (1023 + 7);\r\nsl = (sfi >> 47) & 31;\r\n<\/pre>\n
There’s some subtleties (there always is). I’ll break it down…<\/p>\n
\r\ndouble sf = (int64_t)size;\r\n<\/pre>\n
Convert size<\/span> to a double, with an explicit cast. size<\/span> has type size_t<\/span>, but using TLSF from github.com\/mattconte\/tlsf<\/a>, the largest supported allocation on 64bit architecture is 2^32 bytes – comfortably less than the precision provided by the double<\/span> type. If you need your TLSF allocator to allocate chunks bigger than 2^53, this isn’t the technique for you :)<\/p>\n
I first tried using float<\/span> (not double<\/span>), which can provide correct results — but only if the rounding mode happens to be set correctly.\u00a0double<\/span> is easier.<\/p>\n
The cast to (int64_t)<\/span> results in better codegen on x86: without it, the compiler will generate a full 64bit unsigned conversion, and there is no single instruction for that.<\/p>\n
The cast tells the compiler to (in effect) consider the bits of size<\/span> as if they were a two’s complement signed value — and there is an SSE instruction to handle that case (cvtsi2sdq<\/span> or similar). Again, with the implementation we’re using\u00a0size<\/span> can’t be that big, so this will do the Right Thing.<\/p>\n
\r\nuint64_t sfi;\r\nmemcpy(&sfi, &sf, 8);\r\n<\/pre>\n
Copy the 8 bytes of the double into an unsigned integer variable.\u00a0There are a lot of ways that C\/C++ programmers copy bits from floating point to integer – some of them are well defined :) memcpy() does what we want, and any moderately respectable compiler knows how to select decent instructions to implement it.<\/p>\n
Now we have floating point bits in an integer register, consisting of one sign bit (always zero for this, because size is always positive), eleven exponent bits (offset by 1023), and 52 bits of significant fraction. All we need to do is extract those, and we’re done :)<\/p>\n
\r\nfl = (sfi >> 52) - (1023 + 7);\r\n<\/pre>\n
Extract the exponent: shift it down (ignoring the always-zero sign bit), subtract the offset (1023), and that 7 we saw earlier, at the same time.<\/p>\n
\r\nsl = (sfi >> 47) & 31;\r\n<\/pre>\n
Extract the five most significant bits of the fraction – we do need to mask out the exponent.<\/p>\n
And, just like that*, we have mapping_insert()<\/span>, implemented in terms of integer -> floating point conversion.<\/p>\n
* Actual code (rather than fragments) may be included in a later post…<\/p>\n","protected":false},"excerpt":{"rendered":"
[Previously] This post contains the same material as\u00a0this thread of tweets, with a few minor edits. In IEEE754, floating point numbers are represented like this: \u00b12\u207f\u207f\u207f\u00d71.sss… nnn is the exponent, which is floor(log2(size))\u00a0— which happens to be the fl value computed by TLSF. sss… is the significand fraction: the part that follows the decimal point, … Continue reading “A little bit of floating point in a memory allocator \u2014 Part 2: The floating point”<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,26],"tags":[],"_links":{"self":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts\/1744"}],"collection":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1744"}],"version-history":[{"count":10,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts\/1744\/revisions"}],"predecessor-version":[{"id":1755,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=\/wp\/v2\/posts\/1744\/revisions\/1755"}],"wp:attachment":[{"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1744"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1744"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/brnz.org\/hbr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1744"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}