[webkit-dev] Proposal for serializing alpha channel values; request for algorithm help

Filip Pizlo fpizlo at apple.com
Wed Nov 4 10:22:51 PST 2015


> On Nov 4, 2015, at 10:03 AM, Alfonso Guerra <huperniketes at gmail.com> wrote:
> 
> Gavin,
> 
> That's impressive problem-solving and analytical work.
> 
> However, for performance reasons the pre-increment (and pre-decrement) operators are preferable unless one actually needs to obtain a variable's value before updating it.
> 
> 
> void fasterUnsignedCharToFloatString(unsigned char uc, char* out)
> {
>     const unsigned char* data = unsignedCharToFloatData[uc];
> 
>     *out   = '0' + (uc == 255);
>     *++out = '.';
>     *++out = '0' + (data[0] >> 4);
>     *++out = '0' + (data[0] & 0xF);
>     *++out = '0' + (data[1] >> 4);
>     *++out = '0' + (data[1] & 0xF);
>     *++out = '0' + (data[2] >> 4);
>     *++out = '0' + (data[2] & 0xF);
> 
>     // Remove trailing zeros.
>     while (*out == '0')
>         --out;
> 
>     if (*out == '.')
>         --out;
> 
>     *++out = '\0';
> }
> 
> was ~20% faster on my machine.

It’s very surprising that this made any difference.  Compilers are ordinarily smart enough to understand the equivalence of ++x and x++ if the result is unused.  Are you sure you compiled with optimizations enabled?

-Filip


> 
> 
> Alfonso
> 
> 
> 
> On Wed, Nov 4, 2015 at 1:29 AM, Gavin Barraclough <barraclough at apple.com <mailto:barraclough at apple.com>> wrote:
> I’m too addicted to this.
> 
> I tested a few variants of BCD conversion, and based on some quick benchmarking on my machine it appears any would be a 40X – 50X improvement compared to an equivalent sprintf(_, “%f”, x/255.0).
> 
> The following chart shows the speedup, table size required to hold the BCD, and resulting string lengths for a few different policies.
> 
> Precision
> Speedup vs
> sprintf
> Table Size
> String Length,
> Min
> String Length,
> Average
> String Length,
> Max
> default,
> with trailing zeros
> ~50X
> 768 bytes
> 8
> 8
> 8
> default,
> no trailing zeros
> ~40X
> 768 bytes
> 1
> 7.8
> 8
> ±1% tolerance
> ~40X
> 768 bytes
> 1
> 6.1
> 7
> ±5% tolerance
> ~45X
> 512 bytes
> 1
> 5.5
> 6
> minimal
> ~45X
> 512 bytes
> 1
> 4.5
> 5
> 
> The first configuration matches printf default precision.
> The second maintains the same accuracy but strips trailing zeros.
> The third ensures accuracy within ±1% of the granularity of the step between values – so 1 converts to 0.003922 ±0.00003922, and 2 converts to 0.007843 ±0.00003922, etc.
> The fourth is similar, with slightly looser tolerance.
> The fifth is the minimal precision required for values to round trip.
> 
> Code for default precision with no trailing zeros below.
> 
> cheers,
> G.
> 
> 
> 
> void unsignedCharToFloatString(unsigned char uc, char* out)
> {
>     const unsigned char* data = unsignedCharToFloatData[uc];
> 
>     *out++ = uc == 255 ? '1' : '0';
>     *out++ = '.';
>     *out++ = '0' + (data[0] >> 4);
>     *out++ = '0' + (data[0] & 0xF);
>     *out++ = '0' + (data[1] >> 4);
>     *out++ = '0' + (data[1] & 0xF);
>     *out++ = '0' + (data[2] >> 4);
>     *out++ = '0' + (data[2] & 0xF);
> 
>     // Remove trailing zeros.
>     while (out[-1] == '0')
>         --out;
>     if (out[-1] == '.')
>         --out;
> 
>     *out = '\0';
> }
> 
> static const unsigned char unsignedCharToFloatData[256][3] = {
>     { 0x00, 0x00, 0x00 },
>     { 0x00, 0x39, 0x22 },
>     { 0x00, 0x78, 0x43 },
>     { 0x01, 0x17, 0x65 },
>     { 0x01, 0x56, 0x86 },
>     { 0x01, 0x96, 0x08 },
>     { 0x02, 0x35, 0x29 },
>     { 0x02, 0x74, 0x51 },
>     { 0x03, 0x13, 0x73 },
>     { 0x03, 0x52, 0x94 },
>     { 0x03, 0x92, 0x16 },
>     { 0x04, 0x31, 0x37 },
>     { 0x04, 0x70, 0x59 },
>     { 0x05, 0x09, 0x80 },
>     { 0x05, 0x49, 0x02 },
>     { 0x05, 0x88, 0x24 },
>     { 0x06, 0x27, 0x45 },
>     { 0x06, 0x66, 0x67 },
>     { 0x07, 0x05, 0x88 },
>     { 0x07, 0x45, 0x10 },
>     { 0x07, 0x84, 0x31 },
>     { 0x08, 0x23, 0x53 },
>     { 0x08, 0x62, 0x75 },
>     { 0x09, 0x01, 0x96 },
>     { 0x09, 0x41, 0x18 },
>     { 0x09, 0x80, 0x39 },
>     { 0x10, 0x19, 0x61 },
>     { 0x10, 0x58, 0x82 },
>     { 0x10, 0x98, 0x04 },
>     { 0x11, 0x37, 0x25 },
>     { 0x11, 0x76, 0x47 },
>     { 0x12, 0x15, 0x69 },
>     { 0x12, 0x54, 0x90 },
>     { 0x12, 0x94, 0x12 },
>     { 0x13, 0x33, 0x33 },
>     { 0x13, 0x72, 0x55 },
>     { 0x14, 0x11, 0x76 },
>     { 0x14, 0x50, 0x98 },
>     { 0x14, 0x90, 0x20 },
>     { 0x15, 0x29, 0x41 },
>     { 0x15, 0x68, 0x63 },
>     { 0x16, 0x07, 0x84 },
>     { 0x16, 0x47, 0x06 },
>     { 0x16, 0x86, 0x27 },
>     { 0x17, 0x25, 0x49 },
>     { 0x17, 0x64, 0x71 },
>     { 0x18, 0x03, 0x92 },
>     { 0x18, 0x43, 0x14 },
>     { 0x18, 0x82, 0x35 },
>     { 0x19, 0x21, 0x57 },
>     { 0x19, 0x60, 0x78 },
>     { 0x20, 0x00, 0x00 },
>     { 0x20, 0x39, 0x22 },
>     { 0x20, 0x78, 0x43 },
>     { 0x21, 0x17, 0x65 },
>     { 0x21, 0x56, 0x86 },
>     { 0x21, 0x96, 0x08 },
>     { 0x22, 0x35, 0x29 },
>     { 0x22, 0x74, 0x51 },
>     { 0x23, 0x13, 0x73 },
>     { 0x23, 0x52, 0x94 },
>     { 0x23, 0x92, 0x16 },
>     { 0x24, 0x31, 0x37 },
>     { 0x24, 0x70, 0x59 },
>     { 0x25, 0x09, 0x80 },
>     { 0x25, 0x49, 0x02 },
>     { 0x25, 0x88, 0x24 },
>     { 0x26, 0x27, 0x45 },
>     { 0x26, 0x66, 0x67 },
>     { 0x27, 0x05, 0x88 },
>     { 0x27, 0x45, 0x10 },
>     { 0x27, 0x84, 0x31 },
>     { 0x28, 0x23, 0x53 },
>     { 0x28, 0x62, 0x75 },
>     { 0x29, 0x01, 0x96 },
>     { 0x29, 0x41, 0x18 },
>     { 0x29, 0x80, 0x39 },
>     { 0x30, 0x19, 0x61 },
>     { 0x30, 0x58, 0x82 },
>     { 0x30, 0x98, 0x04 },
>     { 0x31, 0x37, 0x25 },
>     { 0x31, 0x76, 0x47 },
>     { 0x32, 0x15, 0x69 },
>     { 0x32, 0x54, 0x90 },
>     { 0x32, 0x94, 0x12 },
>     { 0x33, 0x33, 0x33 },
>     { 0x33, 0x72, 0x55 },
>     { 0x34, 0x11, 0x76 },
>     { 0x34, 0x50, 0x98 },
>     { 0x34, 0x90, 0x20 },
>     { 0x35, 0x29, 0x41 },
>     { 0x35, 0x68, 0x63 },
>     { 0x36, 0x07, 0x84 },
>     { 0x36, 0x47, 0x06 },
>     { 0x36, 0x86, 0x27 },
>     { 0x37, 0x25, 0x49 },
>     { 0x37, 0x64, 0x71 },
>     { 0x38, 0x03, 0x92 },
>     { 0x38, 0x43, 0x14 },
>     { 0x38, 0x82, 0x35 },
>     { 0x39, 0x21, 0x57 },
>     { 0x39, 0x60, 0x78 },
>     { 0x40, 0x00, 0x00 },
>     { 0x40, 0x39, 0x22 },
>     { 0x40, 0x78, 0x43 },
>     { 0x41, 0x17, 0x65 },
>     { 0x41, 0x56, 0x86 },
>     { 0x41, 0x96, 0x08 },
>     { 0x42, 0x35, 0x29 },
>     { 0x42, 0x74, 0x51 },
>     { 0x43, 0x13, 0x73 },
>     { 0x43, 0x52, 0x94 },
>     { 0x43, 0x92, 0x16 },
>     { 0x44, 0x31, 0x37 },
>     { 0x44, 0x70, 0x59 },
>     { 0x45, 0x09, 0x80 },
>     { 0x45, 0x49, 0x02 },
>     { 0x45, 0x88, 0x24 },
>     { 0x46, 0x27, 0x45 },
>     { 0x46, 0x66, 0x67 },
>     { 0x47, 0x05, 0x88 },
>     { 0x47, 0x45, 0x10 },
>     { 0x47, 0x84, 0x31 },
>     { 0x48, 0x23, 0x53 },
>     { 0x48, 0x62, 0x75 },
>     { 0x49, 0x01, 0x96 },
>     { 0x49, 0x41, 0x18 },
>     { 0x49, 0x80, 0x39 },
>     { 0x50, 0x19, 0x61 },
>     { 0x50, 0x58, 0x82 },
>     { 0x50, 0x98, 0x04 },
>     { 0x51, 0x37, 0x25 },
>     { 0x51, 0x76, 0x47 },
>     { 0x52, 0x15, 0x69 },
>     { 0x52, 0x54, 0x90 },
>     { 0x52, 0x94, 0x12 },
>     { 0x53, 0x33, 0x33 },
>     { 0x53, 0x72, 0x55 },
>     { 0x54, 0x11, 0x76 },
>     { 0x54, 0x50, 0x98 },
>     { 0x54, 0x90, 0x20 },
>     { 0x55, 0x29, 0x41 },
>     { 0x55, 0x68, 0x63 },
>     { 0x56, 0x07, 0x84 },
>     { 0x56, 0x47, 0x06 },
>     { 0x56, 0x86, 0x27 },
>     { 0x57, 0x25, 0x49 },
>     { 0x57, 0x64, 0x71 },
>     { 0x58, 0x03, 0x92 },
>     { 0x58, 0x43, 0x14 },
>     { 0x58, 0x82, 0x35 },
>     { 0x59, 0x21, 0x57 },
>     { 0x59, 0x60, 0x78 },
>     { 0x60, 0x00, 0x00 },
>     { 0x60, 0x39, 0x22 },
>     { 0x60, 0x78, 0x43 },
>     { 0x61, 0x17, 0x65 },
>     { 0x61, 0x56, 0x86 },
>     { 0x61, 0x96, 0x08 },
>     { 0x62, 0x35, 0x29 },
>     { 0x62, 0x74, 0x51 },
>     { 0x63, 0x13, 0x73 },
>     { 0x63, 0x52, 0x94 },
>     { 0x63, 0x92, 0x16 },
>     { 0x64, 0x31, 0x37 },
>     { 0x64, 0x70, 0x59 },
>     { 0x65, 0x09, 0x80 },
>     { 0x65, 0x49, 0x02 },
>     { 0x65, 0x88, 0x24 },
>     { 0x66, 0x27, 0x45 },
>     { 0x66, 0x66, 0x67 },
>     { 0x67, 0x05, 0x88 },
>     { 0x67, 0x45, 0x10 },
>     { 0x67, 0x84, 0x31 },
>     { 0x68, 0x23, 0x53 },
>     { 0x68, 0x62, 0x75 },
>     { 0x69, 0x01, 0x96 },
>     { 0x69, 0x41, 0x18 },
>     { 0x69, 0x80, 0x39 },
>     { 0x70, 0x19, 0x61 },
>     { 0x70, 0x58, 0x82 },
>     { 0x70, 0x98, 0x04 },
>     { 0x71, 0x37, 0x25 },
>     { 0x71, 0x76, 0x47 },
>     { 0x72, 0x15, 0x69 },
>     { 0x72, 0x54, 0x90 },
>     { 0x72, 0x94, 0x12 },
>     { 0x73, 0x33, 0x33 },
>     { 0x73, 0x72, 0x55 },
>     { 0x74, 0x11, 0x76 },
>     { 0x74, 0x50, 0x98 },
>     { 0x74, 0x90, 0x20 },
>     { 0x75, 0x29, 0x41 },
>     { 0x75, 0x68, 0x63 },
>     { 0x76, 0x07, 0x84 },
>     { 0x76, 0x47, 0x06 },
>     { 0x76, 0x86, 0x27 },
>     { 0x77, 0x25, 0x49 },
>     { 0x77, 0x64, 0x71 },
>     { 0x78, 0x03, 0x92 },
>     { 0x78, 0x43, 0x14 },
>     { 0x78, 0x82, 0x35 },
>     { 0x79, 0x21, 0x57 },
>     { 0x79, 0x60, 0x78 },
>     { 0x80, 0x00, 0x00 },
>     { 0x80, 0x39, 0x22 },
>     { 0x80, 0x78, 0x43 },
>     { 0x81, 0x17, 0x65 },
>     { 0x81, 0x56, 0x86 },
>     { 0x81, 0x96, 0x08 },
>     { 0x82, 0x35, 0x29 },
>     { 0x82, 0x74, 0x51 },
>     { 0x83, 0x13, 0x73 },
>     { 0x83, 0x52, 0x94 },
>     { 0x83, 0x92, 0x16 },
>     { 0x84, 0x31, 0x37 },
>     { 0x84, 0x70, 0x59 },
>     { 0x85, 0x09, 0x80 },
>     { 0x85, 0x49, 0x02 },
>     { 0x85, 0x88, 0x24 },
>     { 0x86, 0x27, 0x45 },
>     { 0x86, 0x66, 0x67 },
>     { 0x87, 0x05, 0x88 },
>     { 0x87, 0x45, 0x10 },
>     { 0x87, 0x84, 0x31 },
>     { 0x88, 0x23, 0x53 },
>     { 0x88, 0x62, 0x75 },
>     { 0x89, 0x01, 0x96 },
>     { 0x89, 0x41, 0x18 },
>     { 0x89, 0x80, 0x39 },
>     { 0x90, 0x19, 0x61 },
>     { 0x90, 0x58, 0x82 },
>     { 0x90, 0x98, 0x04 },
>     { 0x91, 0x37, 0x25 },
>     { 0x91, 0x76, 0x47 },
>     { 0x92, 0x15, 0x69 },
>     { 0x92, 0x54, 0x90 },
>     { 0x92, 0x94, 0x12 },
>     { 0x93, 0x33, 0x33 },
>     { 0x93, 0x72, 0x55 },
>     { 0x94, 0x11, 0x76 },
>     { 0x94, 0x50, 0x98 },
>     { 0x94, 0x90, 0x20 },
>     { 0x95, 0x29, 0x41 },
>     { 0x95, 0x68, 0x63 },
>     { 0x96, 0x07, 0x84 },
>     { 0x96, 0x47, 0x06 },
>     { 0x96, 0x86, 0x27 },
>     { 0x97, 0x25, 0x49 },
>     { 0x97, 0x64, 0x71 },
>     { 0x98, 0x03, 0x92 },
>     { 0x98, 0x43, 0x14 },
>     { 0x98, 0x82, 0x35 },
>     { 0x99, 0x21, 0x57 },
>     { 0x99, 0x60, 0x78 },
>     { 0x00, 0x00, 0x00 },
> };
> 
> 
> 
> 
> 
>> On Nov 3, 2015, at 11:37 AM, Darin Adler <darin at apple.com <mailto:darin at apple.com>> wrote:
>> 
>>> On Nov 3, 2015, at 11:10 AM, Maciej Stachowiak <mjs at apple.com <mailto:mjs at apple.com>> wrote:
>>> 
>>> Minimal strings should round trip ok, but will it still be accurate enough if the client attempts to do math with them?
>> 
>> I was thinking about the same thing this morning.
>> 
>> If we don’t want them minimal, then how many digits of precision would be the right number? I think we currently are just using the printf default precision.
>> 
>> — Darin
>> _______________________________________________
>> webkit-dev mailing list
>> webkit-dev at lists.webkit.org <mailto:webkit-dev at lists.webkit.org>
>> https://lists.webkit.org/mailman/listinfo/webkit-dev <https://lists.webkit.org/mailman/listinfo/webkit-dev>
> 
> 
> _______________________________________________
> webkit-dev mailing list
> webkit-dev at lists.webkit.org <mailto:webkit-dev at lists.webkit.org>
> https://lists.webkit.org/mailman/listinfo/webkit-dev <https://lists.webkit.org/mailman/listinfo/webkit-dev>
> 
> 
> _______________________________________________
> webkit-dev mailing list
> webkit-dev at lists.webkit.org
> https://lists.webkit.org/mailman/listinfo/webkit-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.webkit.org/pipermail/webkit-dev/attachments/20151104/0dc39116/attachment-0001.html>


More information about the webkit-dev mailing list