Re: Radix tree for character conversion

On 11/09/2016 10:38 AM, Kyotaro HORIGUCHI wrote:
> Thanks. The attached patch contains the patch by perlcritic.
>
> 0001,2,3 are Heikki's patch that are not modified since it is
> first proposed. It's a bit too big so I don't attach them to this
> mail (again).
>
> https://www.postgresql.org/message-id/08e7892a-d55c-eefe-76e6-7910bc8dd1f3@iki.fi

I've now pushed these preliminary patches, with the applicable fixes 
from you and Daniel. The attached patch is now against git master.

> 0004 is radix-tree stuff, applies on top of the three patches
> above.

I've spent the last couple of days reviewing this. While trying to 
understand how it works, I ended up dismantling, rewriting, and putting 
back together most of the added perl code. Attached is a new version, 
with more straightforward logic, making it more understandable. I find 
it more understandable, anyway, I hope it's not only because I wrote it 
myself :-). Let me know what you think.

In particular, I found the explanations of flat and segmented tables 
really hard to understand. So in this version, the radix trees for a 
conversion are stored completely in one large array. Leaf and 
intermediate levels are all in the same array. When reading this 
version, please note that I'm not sure if I mean the same thing with 
"segment" that you did in your version.

I moved the "lower" and "upper" values in the structs. Also, there are 
now also separate "lower" and "upper" values for the leaf levels of the 
trees, for 1- 2-, 3- and 4-byte inputs. This made a huge difference to 
the size of gb18030_to_utf8_radix.map, in particular: the source file 
shrank from about 2 MB to 1/2 MB. In that conversion, the valid range 
for the last byte of 2-byte inputs is 0x40-0xfe, and the valid range for 
the last byte of 4-byte inputs is 0x30-0x39. With the old patch version, 
the "chars" range was therefore 0x30-0xfe, to cover both of those, and 
most of the array was filled with zeros. With this new patch version, we 
store separate ranges for those, and can leave out most of the zeros.

There's a segment full of zeros at the beginning of each conversion 
array now. The purpose of that is that when traversing the radix tree, 
you don't need to check each intermediate value for 0. If you follow a 0 
offset, it simply points to the dummy all-zeros segments in the 
beginning. Seemed like a good idea to shave some cycles, although I'm 
not sure if it made much difference in reality.

I optimized pg_mb_radix_conv() a bit, too. We could do more. For 
example, I think it would save some cycles to have specialized versions 
of UtfToLocal and LocalToUtf, moving the tests for whether a combined 
character map and/or conversion callback is used, out of the loop. They 
feel a bit ugly too, in their current form...

I need a break now, but I'll try to pick this up again some time next 
week. Meanwhile, please have a look and tell me what you think.

- Heikki