[PATCH] Use 128-bit math to accelerate numeric division, when 8 < divisor digits <= 16
Hi,
On platforms where we support 128bit integers, we could accelerate division
when the number of digits in the divisor is larger than 8 and less than or
equal to 16 digits, i.e. when the divisor that fits in a 64-bit integer but would
not fit in a 32-bit integer.
This patch adds div_var_int64(), which is similar to the existing div_var_int(),
but accepts a 64-bit divisor instead of a 32-bit divisor.
The new function is used within div_var() and div_var_fast().
To measure the effect, we need a volatile wrapper function for numeric_div(),
to avoid it being cached since it's immutable:
CREATE OR REPLACE FUNCTION numeric_div_volatile(numeric,numeric)
RETURNS numeric LANGUAGE internal AS 'numeric_div';
We can then use generate_series() to measure the execution time for lots of
executions. This does not account for the overhead of generate_series() and
count(), but that's okay since the overhead is the same in both measurements,
so the relative difference is still correct.
--
-- Division when the divisor is 8 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',8)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 1633.722 ms (HEAD)
-- Execution Time: 1680.228 ms (div_var_int64.patch)
--
-- Division when the divisor is 9 digits should be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',9)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 5444.755 ms (HEAD)
-- Execution Time: 1604.967 ms (div_var_int64.patch)
--
-- Division when the divisor is 16 digits should also be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',16)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 6072.683 ms (HEAD)
-- Execution Time: 3215.686 ms (div_var_int64.patch)
--
-- Division when the divisor is 17 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
repeat('1',131071)::numeric,
repeat('3',17)::numeric
)) FROM generate_series(1,1e4);
-- Execution Time: 6948.150 ms (HEAD)
-- Execution Time: 7010.544 ms (div_var_int64.patch)
--
-- Same tests as above, but with a single digit dividend,
-- and 1e7 executions instead of just 1e4.
--
--
-- Division when the divisor is 8 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',8)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 1827.567 ms (HEAD)
-- Execution Time: 1828.029 ms (div_var_int64.patch)
--
-- Division when the divisor is 9 digits should be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',9)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 2314.851 ms (HEAD)
-- Execution Time: 1886.170 ms (div_var_int64.patch)
--
-- Division when the divisor is 16 digits should also be faster:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',16)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 2244.009 ms (HEAD)
-- Execution Time: 1968.148 ms (div_var_int64.patch)
--
-- Division when the divisor is 17 digits should be unchanged:
--
EXPLAIN ANALYZE
SELECT count(numeric_div_volatile(
1,
repeat('3',17)::numeric
)) FROM generate_series(1,1e7);
-- Execution Time: 2334.896 ms (HEAD)
-- Execution Time: 2338.141 ms (div_var_int64.patch)
The graph below shows the effect on execution time for numeric_div(),
and also looks at numeric_mod() since it's a heavy user of numeric_div().
The graph was produced by generating 100 random numeric integer values
for each combination of number of dividend/divisor digits between 1 to 20.
In total, that's 20*20*100*2=80000 test values.
As expected, the ceiling for the fast short division is lifted from 8 to 16 divisor digits,
and speedups for modulus is noticed in the same region.
The graph was produced using results from pg-timeit [1]https://github.com/joelonsql/pg-timeit and R for the plotting.
[1]: https://github.com/joelonsql/pg-timeit
/Joel
Attachments:
image.pngimage/png; name=image.pngDownload
�PNG
IHDR � � �1� iCCPkCGColorSpaceGenericRGB 8��U]hU>���+$�������5��lR�����e�m�,�l�A�����i&3���i)>A������[�'!j���-��P��(���G�� ��3����k�������~��s����,[��%,�-��������:t�}�
}�-+��*�&������ �������g��PG�����8�"�e ���]�A�� �b� �;l� ��� W������2�_E,(�������#�Zs���<5��)"�E�6��N#�����E�k���O��0}����*r����U��t��.i���e�i �# ]���r
�>�cU{��t��7��+���g��xu�<���D��1_�
u~R�� ��*-�z�#�Mi*���Wh6������f}�-gi:��9�f�A,����V�>�W���B�_-��%=�^�t�0u���vW����9�%/V��B�W�'�_�t����M�������P���\>����@��y�0`D� i|[`��
�h���h�������)�� �Tj�����0B��#�����hU#�~yh�u� fp#�1I/I���"��0!� �'�Sd�d�:J5��"sd����y#R�7����wA��gd�����J�7����k���n^:}nW��FV���s�t$gj-t����r���_���_�7Z�~��V�5�4�V
}�o[�G�=Nd>�-Ula���Y5V�� }�x�g[����?�k���&���>��s�r�q���]�.r_r_qs�Gj�y�4k����
�i�Q��BZ�-<(d�=���dKO��� a/zv7��]���od�}���s�n����?TF�'|���3Nn��#I?"�m�z����v~K=����s�l<b|_|4>?�p����Q���r�����i����������b
�2*���(��������h� �{28�oI���y�es�8�';�Z�9����h�6�g��� �>�x�Rx'�b�8����WO����[xn%� �|�^���z}��� ����%x�c�� 8eXIfMM * �i � �� �
E @ IDATx�������bAT@i��������b����^���{/�W�?��
��{C��Q�b/ *�?o��?;;�;�����y����d��O2��3''- ��H�H�H�H�H�H�H�H�H�H��#a:&# M��ev �T�XN���I�H�H�H�H�H�H�H�H�H��Xf HE���T���H�H�H�H�H�H�H�H�H�H��e� �T�XN���I�H�H�H�H�H�H�H�H�H��Xf HE���T���H�H�H�H�H�H�H�H�H�H��e� �T�XN���I�H�H�H�H�H�H�H�H�H��Xf HE���T���H�H�H�H�H�H�H�H�H�H�%� ��!��'��~�A�v��Mu���j�_��o�/��B�9R}��g��?�P]�vU��wW{��g~b��@�~���=[�?�RXu�UU�-�~5���w��j�����NP�/���k��!j��qj�-�P�������#P�M��> T�Z�Ob����k�c]���%� � 4!���H���b0�����k ���Cl�F9@�[��;���sN�?L?Yr�%�g��$�h��f��9�������>�Y���:K�&�������r�������[�D�f���?������@5���$Vy�K��8�U��X" � �@��+�&���*7'�w�}Wm������� ��5Y80l��q���W���K��
+��1�H�v ���[�����^v�ej�9��������v�i'm�|�A�n%( � !��� & O������
�@��:u�Zy���3�<S{�UX"�H���OWbm�O�{����J=�����GQ��zj�y �@U��>az�6�l�z���'�E]�Z�l��x� u�M7�g � �:�u��B��H�H�����v#U�u!�'���_*�LFh������_�I�L���sqp�5�P�,�Ld�z�$�����G�7�p�:���g�3H D����/���m��qf�y����������1��ex��7�>G(�o��F��];��{���;F%k��bm�t@����]������XW��aA$@$@$��Xf' �& �T��(Y�o��������^�XH�>g�A�K �"$k����Zl���7�|���rK������G���ZJ����SN��3bOh����M���$�����:�:��I�H�H {t��=c�@$@uM��?����i��ns�H�~�z��Z������g��j�5��i���Z��)x� �@��XW#
A1H�H���@���i�U��/���K1�����W?���j���Zb�%�������~����;Qi�A��������cm��k��3���^xA=������?V��3�Zg�u�_���u2����_���V[M-�����%m����j�� �o�����*����7��Bnp���+����^X����v?ju�_I�b�J�+���������_M�4I��a�i^����F������~��G���r���n�^�z�9��S��
j&����1c���bM�����;����V����M�1e���k���>����S'��J+�����������w�}��]w�u��s���?��3�_|�E5�\s)���W_]!�r��/�������\�s����S�'OV-���y��w����V��>���aE�6�v�m-7}���~.����V�~���v�/�������u<�r��}��
���M�e����������{���v���|\���+[��T��)m��oJK
�,~q_�4zX��z������y�W�,��s�P����\,���.���_V?���6l�:�������x)�@n�����Zv�.�M�|
m����X�]��a<�������Zh#�)�^�������.\G�� � �@C�0C �b$��Z��n������*G2YH�����\�9����������K�����D�y�e;��C�Y�f{���M#J��|�F�T0�|��<��B&yY��v��������@��io��f����B�r�|�cAp�A��LGD�hN���E���w�yg�����3lZ�OD:�����3��(wmv����M?d��@y�h[ �Qy"N���('����w�����.
�@�:��p����������+;���1��K/)�L���e��q�(�#�.����(rU�W?�+l��v���mQ�����o��0���98��3����]
���E�������F���l��S>�S�vK:��;��>q���y��S>�W_}u���r�q�w������F���F]�9���#
n{�|��ST�Tq�<�����ky�hSW�B����9AnW�f����p��XT�6�q�7|}^{�2�����H�H��� ��1T�����o_��rD,r��
�k���X�b�c���@,m�#F�cq�2X�$�%{������[�<Qv�-�������[�t��,/�"b=�JaS_���r���x(�n�����5����M/�����~����s��G���}_r!3��
����i�F�27'���_�L>^}*S���[�bm��c��_������Ss~��"�R �B:�\7��4i���P�,\���;��������s��
�u���e��@����y�>�i^�ND)�e_}�UP�v�m������6���n>���k�H��V�>��?�m�$�c�a����G��Gb�(=��Cs�nR�r�z�>���4��(��}����r�����������M]m����X�]��a<����Zm����^��|_{�0��^$@$@$�L�X�Pk����L�d��� �E0�;��o��t�w\��g�q�}9���o���� ��3�+<�A1�y9���Kp������-�0`�=����r����%��g��2
/���#����M�������n�x��y^y���6��E�U���dQ��4f��\(��Jw��^@�
����E���.kew#y
S/�PP��� /��9���3�{��+��Z��1��&�;|� gS~�N���e+���~�~i������+�/ �K/�4�U�}�,\��5��Y\E7�pC��n��C�8��&������.�����W?�-���4}��2���x�!&�����|<���[l���`�������n���s>�Q#�+��]�>��?�m�b�����0��������F�0�a,�}}�}�������T�9}��16��+S��s��s�=2�|=������k�g������e����+_3�G�8U��|��}_{�0���a �f#@�r�Z�����/g��^(�x��6-^���)��*
K������U�y�����m���q��@�`m�1��*����JI��U�~Aw���F�x��/��|��Mz�����B,*��k��A9e��6�t���)������",�M9�Z�r���.�r����o��F��f
|<1iai?s�LsX��/EH�������{N��C ������K��I��EXv��l����@�l�6��\r���np�6�,�e��
������6fO���������������J�bu��p����|^�a�*��|����Vl��5�&�I�����^�8w�����m:s���l���������A|�'��Nw�w�s���e�����^���}������O�Q������k������8U���������Wc1� � �@��b�-%\ ��B~g!�,"b����_��6������-S���Cs�A�i�H��c����`KQ,���u�`3e#����Q|�t�hD��X��4�g9*���(M��HP(����
���|Q��L�e�������*T5m�%���i������S�7lQ�&��=�~aXj�������d�"�us�8���
�t4u�{�p��O���/�X��7\%>@������K|�m7}��5��V�>�EJ�n��9�����HBX�����#G<����k;�b���#��/���-+��2�Y���������
���P�{��s-�n��l|�o��9��6�xTocQ5�e���gq�U{�# hFs��C���V������b!����`��/�x�q�����i�v_���mw�4?��S:
��C�{X=�������d"%J�����s�=7�z_, �X�����:�����4���=z��v7P?p@z���W���J�&��=��S����z;���\X�[,�u���:�������U�W J����k��9Vk;����E�%�J,��(�Hu�I'�4���n�7��X���p��e����(�s���#�beG����O� JSv�������J�Pv>�iN�v����W�A����Y�r��D���?��n�8�b3�Y�S�����*�'��b������DY��,n��v�
7�|�P��*�i9i|?�d.;�\��n����/G���|�5�xT�cQ��+�F(���>�k��c]�]�O$@$@�B���f�m�)>��ca�+^X���U�cb�h6��,���8�%��J,��L�U=z��I#�W�0��o����s���4s��e8���6.I�x��h��^%.�~�����n�����7P����%nl(,����o���+�XI��{����������T+s��Z��Q+^b�J���ml�������o#��L K9�_���(���������,�]�v
z�36-�/n_�>��[���,���>�!b^���*����O��[-��b�k���LW2��Gml��&Q���|��Q����e��ld�
q���)�Ku*7��������k��m��������f�jq,
�q%�e���gq���S���p�p�H�H��� �Uhe�#����K%})�F�-���N�x����*�U�~���o�Q���_������v��z2��'O6�E_jLB(�`�Pjp��C���X��� ��&���u��e�?
����Vx��n���%�6m1������
���������H��(XYds��&�hK�X6J�A7�8Nd������T>�i�%��o�d/Q\}Z-��J����S��V�c�+S�k��K|X������IS�������l�L (�e�N-�7�|SH�D��}
R��\�6
���r����w\��Gn����J����{����xZkc��k��� � �@��b��-��K�]|��w�%�rQ:�=�P�2�@����'�i�H���n�����F)�r���?_�eY�K}���Q����= \ ����i�b��.��JM�u�]W���jf7��U��+��5��D�p5i��@���e������cS�D~�T,�y)�!$Z��l�B�S:�g?-TN)���I�.��\�}�}*��Tn���X���D�~�t�h\j(�^�r�Q��|���b����
>���r���������.G�p^Y�7�x���Z}��D�o����\}���2�eq2O �eT,W�ud�0��:�h_��";w��]d�B?
���� d�=�i����!����Zc�5�q�Zy�}�QQ��� I_e�
sJI������.���3m[o��#W��cc�������-��r���XeU*��KYD�f���]��.�Y�o��,NSu��4M�I�f�7�|R'������F+����O���;VTr,-�g�����2���97�o��z��i_����~�U�j��/�K�'�X�2�}<���(���h#��^���]Xw?�90�k��:���& �f!@�rZ��[l��U*�a��#�T[n��V(w��!G���dq/�d8p�>�0�X�� ���P�[��fx�K�Z��D�&�d�.��b['�M0~x�z�
6����)��W�Xx��c��n8O���:`j��O?��I���te���c�b6l�>��oH�*��G���5Un\\-�'���X�#I�;����>KrJ��9Q��s�G~�xmB��&=~�s\n�B�Y=*3�1�>�l��������F�_kcd�������v�D��{}�^���J�� �Z$Px��Z��e�2�{����'�T�^z��t�MUX��4p���������+cv�=�h_�c��U��Fm�����d�.|��|]��l�/���Ksj��X���� �m�p^�����3���S.�$������S��z�:t��6m���-"���m�/��C�v�>�T����EMT�&`�g����F��}����4�Z�� ��9���R(���#��|~���BY&:V���
�R��9n^���DY=%-�P�j�i!�J9V�c�[��Q-�E������gq����;n%��{��W����H�H��� �hy�c0a������f?���_���4����X=#�:���^Sw�}�M
+����W/{h���E�����:'�����������+��-���Nm���.����:+29��{���2�!�������W���s��A�E��S.��s��F��K.��2���#�P��@wJ�����K/��5�}�x��'r���
��o����Fi������~�������o��5���r9>��42J�s,-TN�c[m��M��3�1N����Q�� )v/ ����;���+�6n?�g�����W�M���$m=�E�_-��jq,J�'�H��^�����O���`�<I�H�H�P�\�Vr-};u�T���S��s�=7'M��2����#G�{��W������v�)'wJ��6�LG���s�q�lO�>=V)�����*������P�
�7��P��n�B�y'�p�]��W_}�>��/��B�y����v�l��Fi�r,&X(���a��.��N�5j��H��V�PN
�Z������'����bVD�^������M7�dv��|��F=|�S��7J�H���5���r��rB�|����2�����K���\r�9���{��g��_jD��z��{� ���&`
��jK�u��3P��D��f�F�Sj\=�E�s-�G�8��O�=���>�k��c]�|y> � � �+*�+�r+���-n0�L�b��
(���97�J��6�������W]u��,B�~���@�����w��6l��B��u�����k���u���+�h|��G��'���/�����9GuT^�<��U$� ����/��F��fX6���[�����n`�{��7���(�]�a���m���?����Z�k�x���n��)��g��������U`_y�����������?V;���m��]�jw$��+��E�E�����>��(}#-��h���M_������Xj�+��!��9d�����7>�0���r���]���O�>���_~���6��f������[�[&.�o��@I�/���mZH����y,B]k}<���(m������>�k��c�/���H�H����(�2&���o� �����Yf�@,pq_�n V���G��v}\�������lA ���5e����1O;���s��m��l �Q�X��Zo��] ����z�d��W�6������Dy�ur V���������r����@�tl:Qd��A�(�y��;���t��B�����-u��X'���{���������M��� ��@��l�G��2C���^{�����i����E���[o��h �������r��&�lb� �v�m���@���C=��<h���M#/��L��j�w�i�������7���{/|8���oJa�F���[��������Sf�t�*��#�����DD���="���|�
q�cY������H�n���wT��y����g������[����X���K�q����������1c�|���1�������u���'�s���BV�W^y������?J��xJs�����e_mZ�s���>�"��F�F��\��6U���?|�����k��c��@$@$@�H S*@ J:�E4n[���y�/�PB
&L��
�4���o�?_N�|P�B�����b�i��I+��Td���2����E��fg��������qAK�i�7���K.�+������#�[��m<T#}T@_��3�<��G�@`�Jb�X>��S"��o[t��+(<8����L��W���"��l�y)�in��R�9Y�,�E�}�t�b>�iQP'p�R,��i�I������[��>��M#��>��?�m�$����4iI�N�`�����w�uW�����t�*��������e�I�j�4={���AI.���N��(��Y�]���4\��}���_c�J#_#�G�8U���?|�����k��c��@$@$@�F��0�M�n~�a%���u��M��K�4KR�)�&`;�/�+����_{���h#l�����W_�����T�m�H�����$��]Y�KZ��g�{����:��aj'�\|��y:T���6>���{��Q� �����g��}�e2�"u��Vb��0
�]���A��m��S��v����Sb����+r%�u�0����lc1�[���G�I(
3���~�o����W\q����=�q���B;�/'*��|����yE���y���}#-��h��}�������K}�2y���<���W�\�w�}z���r�����e� xI��
���Zk-��c�$�E���(�����j��bL^�c*W��Q-�E;D�}��}_{��2���I�H�H�f ��&�f�k@�� ���O����Bp�VPb�Z���Xu�t,\��A��M�4I���[��#�@��������<|�_�b����Z����1�4�e���k��CY�����:�-~��\��n���������d���P��O���O����~�[�z�iy��F���+}-�'���X����?e��p�����S}��������J�7���w�m8�~���M
��
��TOm��0�n�<��X�*��^��������Y � � �
*�k�%*,���yK/���E��2W��
1;u�d ���,�H�H�H��J���W�y����s�9'6(x]tQ%�/,���0j�Ml<@$@U"���J�Y, � �@��+�&mz����2c����Sy�?q, X)��� ��l��H�H�H��U�,l�%�������Z����&��u���H�8��'� � �@e P�\Y�5S�L,��"Z��3g�A���v����1c������@$@$@$P_N=�T-�_|��@�I�W�Cp����{�%c< � �$�u5�,�H�H�A �F�6l�j]t�E���N�I�����"^$a���������[�s�=��bQ,Z�@$@$@�H �@q�+�1�zv�����O�>}���?�]a�7~��-sD���-��R�=����}FN"�� $"��(�Lq��+3% �<T,�!i���w�]�1"Q�����[o���U��H�H�� >�����0�<��E}�W�|���K�������5�\�=�P+���,���{+��` (� �����{&��r �| HF��0�qj�Tw�q����{�k�[���ZK
6L�5�J�XJ<@$@$P0��_-���X����/���}��j��6k|<�R�k��j���6�$@��=!?�d8�%��T$@$@$P.Z,�K����2e���=��F�.]T�=T������
� � ������/���6�l3��gO
�'O���\sM��j� � �=�uu��� � �@��b����� � � � � � � � � �@��+�Zk�C$@$@$@$@$@$@$@$@$@5N���o �G$@$@$@$@$@$@$@$@$@�F���Zk�C$@$@$@$@$@$@$@$@$@5N�e��G�R������?�����{���Oq6��;�I�&���YWc�%�P����U���O�?����u��:t�`�U{c���j���V�UW]Uq�s���7��u�|>%�f����-����E�y��v�t�M������G4Frp���~��Z`��2�,�Z�n]R�����?Wh����_�Y���#��Y_�;)�J��T.�# ������A�����4�����k�V�FR�{�����w�������cC��9V��3fX������E9rd�y0�� d���K�H �����[
�����r����{�(C3�4��dR`�L_z��`��6
��o>��h��,���� '����D9~��7��G�r>/�
6� 3fL�||'*v����>dKZ^-�� � � �@}�+��jw$�'�����x��U����Il�J$@
K����'�O<1�6�e&�����c�=��k���y���/��p�����_�K.�D-�������9�y��W��K.����J��o��F^c��U}��Q��w_�1����~�/-cH�H�H��� ]a4KK��$���N��V^ye���V�Z5xmY= �}�8.Cy����o�������S2��V{���S}��U���?�K�q����C�*�]������z����������g���~�I����C�U���?���{�=5z�h%��
�l�3l�0���{������~�F" h^T,7o���MD��#�P�l����k���5�B$@$@�!P��Ro��������M���Zf����������zh������:��c���o�`�
����/� �{�����8������~���Zk-m�����4��r�:�����Q���N��v���m��4��(��}�V��Z�7�90? ��"@�r}��%�����K���H�H�|h�{�_|�>�`�X�/6���UW]e������E�F��V[m5��V��=��vEe����k��'���X�.3\�2`�^YD+��o�v�q��7k����������.��lY6 � � �@�����iK��H�H�H�H !���������/��T���9��3a.���/��������j��6�_Y����x�
��
WI}���)���g�u������@$@$@$@$Ph��q;����z� ���K�bK���Y�����[Nu��1Q�u�]W���g����/��W_�m��QH��:�|�7����78a���������*���e�YF�1G�w���zK}��w:;W��>�L������j�����/���������kVI������_��C=`}��wo�������S:�����h;�����3(+�+YI=6/��_���y�%���$K-�����k����d�m����?�������>�H�o�^[O�������_��4�C��R+��[Q�_}��e�p7e��*0���T�N��J+����S�P�����b�VY������~�7�%-����9��o����|_�����p� ��S�y�mM7y�d��B��e��wW� e���U���-���X���������i���'�q��c<re/g�G>���.�}u����}��?���^zi����z����~ e'
�|�����;.��>�_�����L�}{��!����<�_�&��I���h��C.\���o����|��j+���|0���p��I���*�#OJY�5������ ������<���������{w}
�=�`���G�WN��j���? 0�E�!C� �.��g�[�(]Q`����vZlZy�d��N��"������2��/�����3r��o����<�����w��hD�����9��c���mW����*�EH���_�~�Y�%'�rvD���0�<�F|��/*�u�iQ(�� 2OQ��]vYT66�w~�����;�l���=&/�9��;����������-�p��X���1�1cF�q���fQt��o�9�-�l��
�+Y����{�,0�����SS�o����Q0g�y��72��=�RN�>�-2t�����w��h��c��>e]k0�����ey�T�@>�D��G �:���
�D�n]}�G�N>��j�w����6>�;��(�#��VXa���G5������q������n��_
���n�o����(�mr�0e�}���6����LP���"���W���@�Z$:e��w��p?5A>��x<o�������}��/�06]�>�����e�9�����!��!B��^{�4����U^)�&�1���_ L7c���,c"��,��������)^:����)>m2��l�=��t?�����6����m�
���I^>be�hN<5��rK8���&��X�����HV�Ef^$�����+J|�����72�c �y��u��00��uy V�v���%T Oyy!�w~�*�}���,�"�[��a���
02��[ ��X&G*���G#�X����M�J�um��v[N}M9ba����~�L�������������X�G�����E]T�z���(��c�m\���O�i��;��nS���������>�:X���bQ���/�qt��9����o��sO�nT��#J����������m7_�/I���h��2k%/y��>����y�����s�3�!��%b�8>�% ���=���IN�M������n��?�x��N���h�xa�����c��s�H�H�H��X��@ik�Pf�)q������N���t�H��0<�����W(;���5,���Z� ��Gm��������/�g�}v�����tP ����O�>6
�K�ppe3
(�o��� /O���r���]z����R�����1,b�A����|`A�����/'�q��W�[�|�U,M����p[^y���p�����U,�jkT���Kx��|���?jE;�@����W��U,C�'�K(M>P#����}��kYd�������xQ7/6?��K
���X�C����-��"����g���o�������|����p� �h7���5�^X�p�
�Z��X���R:��# ����i��y��9}`������n��g�M}�G>��j�w������ww-�13�M3�}����`!o�'f��
�|��S����v3u/��%-�pz���4L|���������m?�Gq�a�>|�=V�P�� �-a�^�s���y���o#��_~���c�{��7��$\�x�0`����~�*����U�1����$@$@$@$ T,W��
����?�%������~8/-,D����7!�b&>�5�9����e������� _Q=H����,>dmf#,���o�#�I��o�8�<|/����PI�P���0=�P8��mZ($�!\����LL���5p-�L���s�YZW>�������,��?�z�����I�V�l�����C�_���_L�5�`�*��A�p�����`����i�E��6����k�L
�tg��>�-d��r�?�m��=��_����\6}��^r�%��(�VmZ�[��g=!C����G���j��0�r�:8���p�b�������z��qc���� ���b����r���}~���&��b�����������m�Y[���Y���a�I
L���Qj�y���������0��
#F���L�*�M~I�M%�#I�H�H�H���
���5���o�ts|�M7���|�t��4ia�������z��5��n���Y����S��s��uo�c7������qV��l� -%@Y������1�������EYf9�$t]�DY-���U$�Q,�nk�/���a9r�H�%�7���U�F�����L�F6��
�{�0`��}^(W���4���y��-�w�Z9������n=�r%n�As}�C! �����p�SJ�]O�������������].��u��w����%�l�
��
tP��&���E�b����sG1�[�qup�����8&i���X�b�H[�B�a��C�J>����rB�& p�b�X��|_���7,��l���c����H��b��cL��� � � �@S�Cn2&�����D1l���O<a6���S����2%������G�M�������V�k�p���q����0n�ac�� J�:N\y��?<�xxi����v���o�T�:m�W^ye��
Q���'���S%/hJCJ,��X/<u���9.��9���+z�YNs�1�p!H�;?[p�
�m-/WJ��u�2%S����@��T@_�'�8�@��,Z|���N:��A��
��T���B��e�s��n�,�C|V��3�>;u�d�@^���k#�������J��v?�F��������0�j��r�:������6<�O�0.�����'�|R�W��m|��j<w$��X�r�_��_���/�����R��L�[!��|(Uw�}���?9��R��4I����qe��f�����8G'�E����(�\�{����8X�1�����H�H�H�1P�\�v�)�J|&���zG��bN�F���];����W\Q��EX�k�b��dQ��|�����7�x�o����Ub�l��!��v_|�*q-`��6V_}u{�=�F��V�����PNyFN�d_��(�?����+i5d���4b�����l��f�n���n��bqf��6|�UF\��V>���+�eh\�:^��
�y����x�uT,l���6����o�K�(�����U�E��\��6�����g�/�[�Xb ���E�
�n:w;�z��r����[olW�����!����mF&qc�?���/���7�|Ez�x��%|��/���V>Y���K��+Y�@��/��#����yY��� 2+�l�u����n�����Y'��MY�����$���|��2Tr�����H�H�H����/q�WZX��q(��������)������&�����>f,>��!���y��7�@d�~�1s�XFc�X]�c��A\D(Xw���{~��$yA�g,V��G��<����$������N3qeHR�*jO���_�,��d�0�n��������V>�Z|�"e�>���x �j��sJ�w_����X^��Q��(�����I��b����:�g�E�I�Z����m�lWq���+�O�}q������(3I���G���0�j��$\��:����#�a��)X�����X��� '���v������h�_W9�s��J?w��/.}��/q��K|��E)����-
�����"��GMHzow�z�5�F�fq�F�����'�Ci�'��e���e=�7 � � �@��b�Bm��v�)Y�E���z�8����:��rS�,[�Y��0�ec�����`�xc����JQ3�1.}8S���B�Ri>y'�����*�������R�
,ddq��CyqIae�7�|S�b9M~y������ a�M|�����:�.('�� �xI6S{?�����I�����"�r�?�m�e{�}��p��<���gYO���O��E3����z'�
������u����#O��x����,�k�M!������X�{��.�(��������������W��K�%���Y�ik �-{�����/����Q�"-�M��b��;���_7]���Y\�q��e%���q8k�r%��86�' h.T,W��1M�s�����g�U�B�4B���Q,�b>�1������Ciie��S3K�]+aXW�Of�P��7m^����L��{8�=0�V��/�������s9��n(uj���w~&_�m
W&&��' �o�$�KM���ZG��R���(\��E��3�W�����x�m�e{d�,.�)|,�z�����?|_������D�v�����{N�b[�/,f���5x�`%|i�PX3�
�����~�����.��=�X=�q=z��kV��B��~����
%���tI�������{��u�&�&Kn��vo���x����S��<�H�H�H�1P�\�v���o��� �F9 @ IDAT�x��"�(���h����Zk������ S���+'�,�*��J��4�W�����iyYd��V6Je�py��z�1�:t�)6�H`!�8,���.\+o(W�������������v-w>���b���.�D'�������O?�4Q.�?�_��"E�2I�(�~�B�������#D����Y�����O�F��j�N+K8���������>���`�B�x.0��^~�eu��'�t����0�f��z�H��?P(��� x.��r�{�YW��C)>`���>/`��RB���+�N��uL*��cd�z�1���H�H�H�� ^U���x�=��� wp���k��(c�l��� P�=���V�U�
�9��_W�0n��r������<,��|�Iu���*��R��}�\e���$/nX���s���2�n�b��s���nk�R�}Q��<�L\_�xa7!�b�M����c����e�-W>�m[�Q.3��u=��!N^7�;~�������o��� ���~�!��x@�rs�]v���h.���&��������2*��" T�ks��p���3�$R*#�|0��0si�� E��k8�^{m�����=�P�n;%q���E�_�Bygq,�1&Y�' � � �@}�b������F�2������b����Ri�+����l�w�+[,�y��j�5��/�g�uV���7�"� Xml�����c7�B\0nI��#������a�^(���PY�c��z����E�E��Qc�oO�p�}D��d�(��v���R�i�����,�m�b�n�zh�r�����Y�����O�������_���p-�z\��n��Zx���Y�7����zz���C��g=^�y�9��+���&;�����������zk��y|���&f�����,�<���{TlAr�W�^�0����w���q�u��B��N��7�1��,,O$ hT,W�)�P��f��'N����5!�X��C�� ,ma����2�X���,~1
.00���#�(X�P&�{���9�<1���eH�N�
�4u�Tu�����1J����w~�a����F�q�mw��w��;��������_Tqq���W��n.�����u�:���c��9�����v����{w�-��
T�|P����l���Fz�����+������(���������������cQ6��$�o�B�]�J�X:'�X��;���Qr7r\1&Y���b��y��g�@�?���9��_?��p�H� {���*uM
��(#S�/�B[!��5KA!�O�^�y#�\_�� ]5�#I�H�H��� �n�m����h���rxaXl`?XAL�6MoW�
��������L@�}��'[k-�������>�(��^@�2R� ?�&@9?e�����x90�����3���~�u�`�C{����v��-�����4����������F��/�x)���;����~���]I^��f6 N�R��7���/f�]v�������_o����?�Xa�����k���n�L�������m��=��e��D=K?|_���I�������,��O9.@Ie�X@7��w^T|5�;���Q27r\1&�/��~����?���1���J
�^q�����f|l�q����h�G�)^j�}�*&���3l�0�,l���saH��Q���U�o�~�L}�1W_}�:��S���7�\��<�H�H�H� ��C �el ��t-�'����6���w
�i���;���\sMl:s�s��6����Mt���{�m�@��W_=��@�:9k�@9i.����<��V�6m��<�#/�$b����X{b-���@��{��7?�����i��$+q�^��9��u0�!��^xa�����?�]|��<d!�@�9���������+����+/��(zs��_mm�_��L�����(|yd�>��A^�mZy)3Y��u��X��"��`�,�������A6�C�e�l�V 8��3�BFq���G���`���������0��%��G]���W{���r�-g�D�
���X��t�+?��Sl�b|���u�1������].>�:X���2
^�G��0����^������@f��B)�<Y ������sG�{K�q9m��y�=����������q������w��9^��#������{s�=w�?q������cY_��+3$�������
�:�C�'�tR^�D��f����N;-�hO������/8�n����,��/>���V��b�����j������'O^F� � � � �"���d��}P��}��)��o���NV��32-"�x1��X*�������N8!R���SlE %j��������#/Z���������^���M���x�V�d�����\����6U��@,�
2��;)b�g���X����&bh���Pp��i�����2���;im��g�E~n_��l�����#M=��X�U�p���|^����i� 8&�����?��c�xo�}����������sG1E�O2.�m7W�V���$L|����a���>�n�)e�X����������U�����c���$�eC)?������Z+g��#a��b�%�7>�*����$@$@$@�
C�n+�i�b��D!)���'{�a�_%�X�(��UX�n�u��]�L�Bu��/����-.9�T�H�i�u����a�L��|��m:���K���E
�OZ^��A���1������J���m���T������D���� �+��@�|T���i����i��{���l���A7��0}Suq������;N��"�_��e��U��%��������-�z�?|_�i�5SE�z�������c�[��/�(�����4|����I���u���I�d5^�q+u����L�X^����7�8�r��Wp
w���z{��}�2u���c�=����:p��u
��e�^g��=z��nF����!I�����.LO$@$@$�8Z@��8�aM�&��'M���z�-�{�g���aY\Bd]tY�CA�X�
�� 7�iD�|�>C�!V���C������z��W�/l�/^���+/�q�m
?��3�;P`a��N+R�����?|<(V�.��/�P���?��Cb������mk�=
�(�`9��z��y�'E�l���_|������B)�T2;))��K�f\����(pR&��%���4�o����~����'�"��e2��e�N�������N���)D�I�M3�1i��iI�H�H���b�G���9�V�w~����H��� ���k3JL$�8���k����^zi%kx�bP���e
�S�N
�3� � � �@#��D���$@$@$@$@$@$��5"����1��$5��;:)��&&��6B���� �z'@������H�H�H�H�H�b`�l����9S
4(�����^�3��~���67H�H�H�H�� �b��[��� � � � � T���G�N:�$]&����O�����R������[�s�=V.,����;�}n� � � �@��b��[��� � � � � T����������#�"����W��}��U��rK�a�� � � �@]�+��l6
]--Z�P��|��K.�C$P�8~�~QB ��&p�w�{��W����]k����a���Q�T��mc�� � � � �#�2U+�G�)3 � � � � � ��)S��O?�T����K�.�G��{��� e �LP�� VfJ$@$@$@$@$@$@$@$@$@�K��0�mY3 �� ��`e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H T,g���� � � � � � � � � �@��b�q��5# �LP�� VfJ$@$@$@$@$@$@$@$@$@�K����m[��H�H�H�H�H�H�H�H�H�2!@�r&X�) � � � � � � � � � 4.*��mY3 �� ��`e�$@$@$@$@$@$@$@$@$@$���Xn��e�H�H�H�H�H�H�H�H�H�H T,g���� � � � � � � � � �@�h��U���M�:U��1�6��$@$@$@^ ,��b�e���S�����<y�WY� � � �@mh���Zh��jCJA$@hH�0�����CUO?�t�s hDO>�����[��=��sj���O}O �}����:���k_PJH$@eHobSf��x:^8��{�f�:�L$@$@
I��?T#F�(�n�r�j��}��0 �� 0x����R� �@P�\��[�V+��RJb$@$@$@� ���z)f���V�.����� � � �@� �5�\��� �@�p��
�f1$@$@$@$@$@$@$@$@$@$�(�Xn��d=H�H�H�H�H�H�H�H�H�H�B�X�hC$@$@$@$@$@$@$@$@$@�B���FiI��H�H�H�H�H�H�H�H�H�*D���
�f1$@$@$@$@$@$@$@$@$@$�(�Xn��d=H�H�H�H�H�H�H�H�H�H�B�X�hC$@$@$@$@$@$@$@$@$@�B���FiI��H�H�H�H�H�H�H�H�H�*D���
�f1$@$@$@$@$@$@$@$@$@$�(�Xn��d=H�H�H�H�H�H�H�H�H�H�B�X�hC$@$@$@$@$@$@$@$@$@�B�e�T�� C��[oU/��������c�=Lt��
7���x�
��&���w��������+��b��ml����o�������{�=5�����/�X�5�\�i���:5a����s�9��g�yT�����k��z����@$@$@i\{��j���j�}������SO��#G�u�]W���?MvM���c�U����:����B-T6�/��R-�����������V|���<y�����n7<{$y�@]x����/�Pg�u�>?��������7�|�Yd���0`������\���kWr><�H�H�H�8*��3b
�:#���_�I�&���Z���S�L�iWZi���&���;��}�Q{�������u���{Nm��F�����( ��:� ��z�J�c$@$@$�C�����������Cy�{O�=l7� |�����_~Q��G|�G�H������_�=:��w�}W�}������S-Z��J�O>�D���K���S�]v����w��O?���)W^'[��������������*m��o�)�e �� ���e�$@uN V����{�Z�Vz��'�Ry�
6Pc��U>�`A��)�O�>j�w4���?��/�x�5j��u�y��������K�t� ���\rI�������iOm����4k�,5�|��U�3f�#F��-�_�~��'u� 'h%)fU���O[�~������X��:��#be������a�b�����\�����Z���� � � (��C*$@$@���.�z��i�K�x��G�ip�z��7����>�L-��b�k��md�����v�q�9�h��A�������{��� � �@�Xe�U�������<���k���:�����2������3�g��]�z���.1���;(���c��Zf�O$@$@$�\�Xn��fmI�*L �d�7�K�.j�
7��]a�\�����s�=�:�����{��>��#u�=���v���i<N$@$�d�k ���
�M�6��O���c���������[5s�L�����
��w����iC�e�=�������n���}h5u�X�`��q
~�����R����
ekcS��/�X`��+�\���]c�����|���z�c(����>�~���V������^[~���u���G��eX3#O���
�YJ��p(���4�����'>F�j�*6[��� ������5.+p��fA?����a�`����~�p�/~�7��������jfnn� � � �N������L (J�X+?��� ?�p�k#,�Wj�����n�[z���J���� � 4 (|�������])�*��p_���p��c��Q�_���,~(��<�H���W_]�b��2�����K�k��K/��������7���>�hw�[� ���w�Y�r�����o���!o0�">~�
�� PB����������{,���
>>��\a������}(zw�a�u�/�����ZK�r�b�� 6��|�I'�&/(���>��#�<��P$8�����v[�N����;�An����!�bOE^x������t���_��kV�v�i
>�M@�{���4@�K$@$@e�b�L�<�H���J��g���7�|s�����k�&X�<��3j�-��;=Q��������a �2n�^~�e�������y5t����8b�p��PP��4l
�_(�_|q��2��eS0��2����T����AX��?^����Yg���PZ�����2����j���.I���������-�4@FXVCq�{?���z�v]�YL:t�Jo(���R�� %4�
UX�CI��kW���f�m�%qXXN_|��Z�������E������rt��Q���������r]|����r��a���V+�������9'NTp���S'������y�a��u(���p���3�Dcv����`���E ��������
��H��*:w�����~�m-�3�d3� � � �G������l �&��SO��B"�i�qi^}�U�{�q��������KK,�����}����SX��\��Y4�����e�c�WF� � �%(P_x���lg�l���Z E\��{|�B��dq.��p.5�R�`�T���P�P�BE%,`a�lf��T����T�&��_(����j��lp�Bn1� �%8�H�x&�b����`����I�H�gX�"�F���KZ{����- �6��
v0���D���J��y�*|�EQC�Qg�y�^$��P�#�J
t`]|�W�g�'�|R�>