[webkit-dev] Proposal for serializing alpha channel values; request for algorithm help
Alfonso Guerra
huperniketes at gmail.com
Wed Nov 4 10:03:27 PST 2015
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.
Alfonso
On Wed, Nov 4, 2015 at 1:29 AM, Gavin Barraclough <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> wrote:
>
> On Nov 3, 2015, at 11:10 AM, Maciej Stachowiak <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
> 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/0d44979b/attachment.html>
More information about the webkit-dev
mailing list