Lazy hash table for XidInMVCCSnapshot (helps Zipfian a bit)
Good day, every one.
In attempt to improve performance of YCSB on zipfian distribution,
it were found that significant time is spent in XidInMVCCSnapshot in
scanning snapshot->xip array. While overall CPU time is not too
noticable, it has measurable impact on scaleability.
First I tried to sort snapshot->xip in GetSnapshotData, and search in a
sorted array. But since snapshot->xip is not touched if no transaction
contention occurs, sorting xip always is not best option.
Then I sorted xip array on demand in XidInMVCCSnapshot only if
search in snapshot->xip occurs (ie lazy sorting). It performs much
better, but since it is O(NlogN), sort's execution time is noticable
for large number of clients.
Third approach (present in attached patch) is making hash table lazily
on first search in xip array.
Note: hash table is not built if number of "in-progress" xids is less
than 60. Tests shows, there is no big benefit from doing so (at least
on Intel Xeon).
For this letter I've tested with pgbench and random_exponential
updating rows from pgbench_tellers (scale=300, so 3000 rows in a table).
Scripts are in attached archive. With this test configuration, numbers
are quite close to numbers from YCSB benchmark workloada.
Test machine is 4xXeon CPU E7-8890 - 72cores (144HT), fsync=on,
synchronous_commit=off.
Results:
clients | master | hashsnap
--------+----------+----------
25 | 67652 | 70017
50 | 102781 | 102074
75 | 81716 | 79440
110 | 68286 | 69223
150 | 56168 | 60713
200 | 45073 | 48880
250 | 36526 | 40893
325 | 28363 | 32497
400 | 22532 | 26639
500 | 17423 | 21496
650 | 12767 | 16461
800 | 9599 | 13483
(Note: if pgbench_accounts is updated (30000000 rows), then exponential
distribution behaves differently from zipfian with used parameter.)
Remarks:
- it could be combined with "Cache data in GetSnapshotData"
https://commitfest.postgresql.org/14/553/
- if CSN ever landed, then there will be no need in this optimization at
all.
PS.
Excuse me for following little promotion of lwlock patch
https://commitfest.postgresql.org/14/1166/
clients | master | hashsnap | hashsnap+lwlock
--------+----------+----------+--------------
25 | 67652 | 70017 | 127601
50 | 102781 | 102074 | 134545
75 | 81716 | 79440 | 128655
110 | 68286 | 69223 | 110420
150 | 56168 | 60713 | 86715
200 | 45073 | 48880 | 68266
250 | 36526 | 40893 | 56638
325 | 28363 | 32497 | 45704
400 | 22532 | 26639 | 38247
500 | 17423 | 21496 | 32668
650 | 12767 | 16461 | 25488
800 | 9599 | 13483 | 21326
With regards,
--
Sokolov Yura aka funny_falcon
Postgres Professional: https://postgrespro.ru
The Russian Postgres Company
Attachments:
0001-Make-hash-table-for-xip-in-XidInMVCCSnapshot.patchtext/x-diff; name=0001-Make-hash-table-for-xip-in-XidInMVCCSnapshot.patchDownload
From f2696dc29bdb46de62e8aab3cf4685fe53de9f3a Mon Sep 17 00:00:00 2001
From: Sokolov Yura <funny.falcon@postgrespro.ru>
Date: Mon, 10 Jul 2017 12:34:48 +0000
Subject: [PATCH] Make hash table for xip in XidInMVCCSnapshot
---
src/backend/storage/ipc/procarray.c | 21 +++++++++-
src/backend/utils/time/tqual.c | 81 +++++++++++++++++++++++++++----------
src/include/access/transam.h | 5 +++
src/include/utils/snapshot.h | 3 ++
4 files changed, 87 insertions(+), 23 deletions(-)
diff --git a/src/backend/storage/ipc/procarray.c b/src/backend/storage/ipc/procarray.c
index a7e8cf2..2a5e3ac 100644
--- a/src/backend/storage/ipc/procarray.c
+++ b/src/backend/storage/ipc/procarray.c
@@ -1533,23 +1533,34 @@ GetSnapshotData(Snapshot snapshot)
*/
if (snapshot->xip == NULL)
{
+ uint32 cap, max;
/*
* First call for this snapshot. Snapshot is same size whether or not
* we are in recovery, see later comments.
*/
+ max = GetMaxSnapshotXidCount();
+ cap = 1;
+ while (cap < max * 2) cap *= 2;
snapshot->xip = (TransactionId *)
- malloc(GetMaxSnapshotXidCount() * sizeof(TransactionId));
+ malloc((max + cap + 1) * sizeof(TransactionId));
if (snapshot->xip == NULL)
ereport(ERROR,
(errcode(ERRCODE_OUT_OF_MEMORY),
errmsg("out of memory")));
+ snapshot->xiphash = snapshot->xip + max;
+ snapshot->xiphash[0] = cap - 1;
Assert(snapshot->subxip == NULL);
+ max = GetMaxSnapshotSubxidCount();
+ cap = 1;
+ while (cap < max * 2) cap *= 2;
snapshot->subxip = (TransactionId *)
- malloc(GetMaxSnapshotSubxidCount() * sizeof(TransactionId));
+ malloc((max + cap + 1) * sizeof(TransactionId));
if (snapshot->subxip == NULL)
ereport(ERROR,
(errcode(ERRCODE_OUT_OF_MEMORY),
errmsg("out of memory")));
+ snapshot->subxiphash = snapshot->subxip + max;
+ snapshot->subxiphash[0] = cap - 1;
}
/*
@@ -1757,6 +1768,12 @@ GetSnapshotData(Snapshot snapshot)
snapshot->active_count = 0;
snapshot->regd_count = 0;
snapshot->copied = false;
+ if (snapshot->xiphash != NULL)
+ {
+ /* set "unbuilt" bit */
+ snapshot->xiphash[0] |= SnapshotHashNotBuilt;
+ snapshot->subxiphash[0] |= SnapshotHashNotBuilt;
+ }
if (old_snapshot_threshold < 0)
{
diff --git a/src/backend/utils/time/tqual.c b/src/backend/utils/time/tqual.c
index f9da9e1..fdf0a1c 100644
--- a/src/backend/utils/time/tqual.c
+++ b/src/backend/utils/time/tqual.c
@@ -1450,6 +1450,59 @@ HeapTupleIsSurelyDead(HeapTuple htup, TransactionId OldestXmin)
return TransactionIdPrecedes(HeapTupleHeaderGetRawXmax(tuple), OldestXmin);
}
+static bool
+XidInXip(TransactionId xid, TransactionId *xip, TransactionId *xiphash, uint32 xcnt)
+{
+ uint32 i = 0;
+ uint32 j, k, d, mask;
+ if (!TransactionIdIsNormal(xid))
+ return false;
+ if (xcnt < 60 || xiphash == NULL)
+ {
+ /* full scan for small snapshots and if xiphash is not allocated */
+ for (; i < xcnt; i++)
+ if (TransactionIdEquals(xid, xip[i]))
+ return true;
+ return false;
+ }
+ mask = xiphash[0];
+ xiphash += 1;
+ if ((mask & SnapshotHashNotBuilt) == 0)
+ {
+ d = xid >> 6;
+ j = k = xid & mask;
+ while (xiphash[j] != InvalidTransactionId)
+ {
+ if (TransactionIdEquals(xiphash[j], xid))
+ return true;
+ j = (k + d) & mask;
+ d = d*5 + 1;
+ }
+ return false;
+ }
+ else
+ {
+ /* build hash */
+ int found = 0;
+ mask &= ~SnapshotHashNotBuilt;
+ xiphash[-1] = mask;
+ memset(xiphash, 0, (mask + 1) * sizeof(TransactionId));
+ for (i = 0; i < xcnt; i++)
+ {
+ found += TransactionIdEquals(xip[i], xid);
+ d = xip[i] >> 6;
+ j = k = xip[i] & mask;
+ while (xiphash[j] != InvalidTransactionId)
+ {
+ j = (k + d) & mask;
+ d = d*5 + 1;
+ }
+ xiphash[j] = xip[i];
+ }
+ return found != 0;
+ }
+}
+
/*
* XidInMVCCSnapshot
* Is the given XID still-in-progress according to the snapshot?
@@ -1463,8 +1516,6 @@ HeapTupleIsSurelyDead(HeapTuple htup, TransactionId OldestXmin)
static bool
XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
{
- uint32 i;
-
/*
* Make a quick range check to eliminate most XIDs without looking at the
* xip arrays. Note that this is OK even if we convert a subxact XID to
@@ -1496,13 +1547,8 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
if (!snapshot->suboverflowed)
{
/* we have full data, so search subxip */
- int32 j;
-
- for (j = 0; j < snapshot->subxcnt; j++)
- {
- if (TransactionIdEquals(xid, snapshot->subxip[j]))
- return true;
- }
+ if (XidInXip(xid, snapshot->subxip, snapshot->subxiphash, snapshot->subxcnt))
+ return true;
/* not there, fall through to search xip[] */
}
@@ -1523,16 +1569,12 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
return false;
}
- for (i = 0; i < snapshot->xcnt; i++)
- {
- if (TransactionIdEquals(xid, snapshot->xip[i]))
- return true;
- }
+
+ if (XidInXip(xid, snapshot->xip, snapshot->xiphash, snapshot->xcnt))
+ return true;
}
else
{
- int32 j;
-
/*
* In recovery we store all xids in the subxact array because it is by
* far the bigger array, and we mostly don't know which xids are
@@ -1562,11 +1604,8 @@ XidInMVCCSnapshot(TransactionId xid, Snapshot snapshot)
* indeterminate xid. We don't know whether it's top level or subxact
* but it doesn't matter. If it's present, the xid is visible.
*/
- for (j = 0; j < snapshot->subxcnt; j++)
- {
- if (TransactionIdEquals(xid, snapshot->subxip[j]))
- return true;
- }
+ if (XidInXip(xid, snapshot->subxip, snapshot->subxiphash, snapshot->subxcnt))
+ return true;
}
return false;
diff --git a/src/include/access/transam.h b/src/include/access/transam.h
index 86076de..b60126c 100644
--- a/src/include/access/transam.h
+++ b/src/include/access/transam.h
@@ -68,6 +68,11 @@
(AssertMacro(TransactionIdIsNormal(id1) && TransactionIdIsNormal(id2)), \
(int32) ((id1) - (id2)) > 0)
+/* compare two XIDs already known to be normal; this is a macro for speed */
+#define NormalTransactionIdCompare(id1, id2) \
+ (AssertMacro(TransactionIdIsNormal(id1) && TransactionIdIsNormal(id2)), \
+ (int32) ((id1) - (id2)))
+
/* ----------
* Object ID (OID) zero is InvalidOid.
*
diff --git a/src/include/utils/snapshot.h b/src/include/utils/snapshot.h
index 074cc81..e0a3b11 100644
--- a/src/include/utils/snapshot.h
+++ b/src/include/utils/snapshot.h
@@ -23,6 +23,7 @@
typedef struct SnapshotData *Snapshot;
#define InvalidSnapshot ((Snapshot) NULL)
+#define SnapshotHashNotBuilt (0x80000000u)
/*
* We use SnapshotData structures to represent both "regular" (MVCC)
@@ -75,6 +76,7 @@ typedef struct SnapshotData
* note: all ids in xip[] satisfy xmin <= xip[i] < xmax
*/
TransactionId *xip;
+ TransactionId *xiphash;
uint32 xcnt; /* # of xact ids in xip[] */
/*
@@ -87,6 +89,7 @@ typedef struct SnapshotData
* out any that are >= xmax
*/
TransactionId *subxip;
+ TransactionId *subxiphash;
int32 subxcnt; /* # of xact ids in subxip[] */
bool suboverflowed; /* has the subxip array overflowed? */
--
1.8.3.1
test_hashsnap.tar.gzapplication/x-gzip; name=test_hashsnap.tar.gzDownload
� �KY�]kod7r���_q�5;���H^x� 1�/��A>�.=���lMk��������{���s9�~�N$`-��y����9�{��/^������������G�\>Sd3�|�xB�\�]�O�h��������z?MO����G�w���G���_����������q{}��V��\�����w�)���7��d����d��g���a{��W��~���y�b�����Df��q���Y_o?��1+���~�/�����W/������L���W����z��l�����4��_����q���3����'���������z��������
����%>~������Kq����o���t���j'7�~������|����@~o{}����Uu���^\������w���O�_�\N�������xx���p|����o����WW�i�z�����8}�r���o��n�g�L��Dd����?L�/��=������@���O.�����gW���������^l����#�}�x������t�����������>��-������,����y��H�D�o�O^�f�_�'�����>��z����6���� ����g����vW~����?��/�����7�LZ��*���sz��������>�fz�����������~{9=�j
�:��g_O��������i�w�����&��EH������}�_���S�l����������N2=����C���0���_��#"X.x��
����}b�����/�q
�W�W�w������j��]�.��5.�7�����p�= �%z>�xe����,%�|}|+��^'�"��o��x)������!����������e�[�1�
�J�2jKgg��<f�Lf�aLOs�6&���1����szvn�%��|L��t��r4����q+��v������Sfk>|m�n��$���bC��i>$�
�2��
��������nD����L���
]������O��������83�w#�����2y="������eK��{�a�#&s6���hl81�}�hh�p�8��(N�?|�|1 ���6�1�<�:���s����2���9E\W?XW��c$u6�pY�i��w�zK�%g
"���-���L$p������<yP���I���s�3�������?�,MV�r�����Q��.[�T��uL�����R��d����YrS@��K ,YY��������Z�3�Y[B81�,��� -�h�X�pr��Y�7��Z�3
ys �%t\���:. �)�K6�7���Y�%'����-�@$e���-��6��D�%�x��5���`�0���+����k��,�|b���>�Mg�F���m�'7^!�,�s�����l]s\�Yj!^k���:���M�q�����-}u\1��M��:V ���O�L����mE"�������$�2:.-����6��U~�e3�����������{��������<:fg
A�,#3��g
�hL#�\W�pD���&�������^:��jr�"�|�<\�����k"��X�1+I��qi�Dn�DY�����H����~a���"�p����Lq�X�eu���C����T!a�������� }�l�@DA���]�0U�EkE"qy����5����H�|r��\^�FY�������7�1�H�![��=��V�_l9���dp�"�XB�r�e�f�W�#��)��p�IF9Qnyu��*@�����!h��-��?�PM�Z����s�L���s�LkE���X�ZR���;e@D�S%���qZ�v\py�����|B �0�����n����rGY��*��#��}C�,"�(l�V�%��
<(%=�1�����M�R��8,1���)Qp�AI�o���'�v��`�jq&�,�'�X(�����L�yaq�\�g&�a����f�ga;�+��oH��";9��L���Q �V��IF�0py�Y����=Qc��H
���S���3o-f�v��s+�J��AA�`[qF%� ��vXT���,�@q���*�V�����
j��8+mQ�s\��X�9+���W�i���L�B�P��>�C�l��Y��`���QzH)��uO��lT�qM���A��D>$I��{��8���m}g��3�r5n
�
�:niMD���*��8����zs���M���n?(4.���0p_����T ^��v��~zss)�g��������~��z�\_�:5f�=��o����{y�_��Os���js;L��v}}��r��G�^���q��r�|����i��v�~U�~�����?�{��O=��Ode������&������ns}{Y�qs��m��.���W����OfvEKw�No�z�����g��7j���]������&�_���%��A!�$�����z:$�S�^�u��Q9�iK���crA��u0����M j<IGa����M�b ��0����&Y���+dz��������-C���%���iK�:�L����ai%F��/q��`jW����"����'"� oZ�(i� Z�WY�Y��#�19��X-���� �G���irI[��H ��5P�zoaL�h d��28��N����fU�6�(�;���Q��:�a���L�'����Tc�s��S���5�d��b����z���*��: k��X����8�7=���*Z@<W�}����U!@�U;�J�\W�iO O\h
D�Fk���F�2�T=)������Y���1P�"/���Q z�iXn\ ��S�+%9n��f2A;��d�K���V�k�<���=��"v9� G�������z ��m�������1I6��R��e�Q?��!�j����� @�7;��d�=E������G^E%���������� ����$��i��l*�GB��
��P�1
��Q���(��F��IJ�YuD)�DD���i���w�h������p,�/��)d�}� ��B�L������ ����p��K��,J�8��U@>Y��
����k�%�~7��U�R�]��[FaL�S�)a��[�L�RO �-���E=�L����(�B�7�{���kd��� �L3��)�/��<X�#�B��K��K����U���RV��@�����Z���u��n@;��K�Tp�6��� kC�1�Lj��H@0X�487�_�#U% G�/z��#�{2�X������V� �,��ui
K��bg�z�*dg�G� �Z�n#��%�����=�@fA5�?��:��
��>�w��k�H��K!�5��1(�z�
����0r��6��%<�T=�
K6�R�F
nV�����aYr����I�
� ����^@kra�LK���
�� �!����*�4g�?�S��X����!%
���g�n�Y5S\���rl�Y3D��
��
c�8%#�-a��:��SO6���� �L�� ����*� ?\W6 �j2��G.�t����zC���
dk�D���p��&L����!+%�o ���]������E���Z��&gP��R��&�r���������KC��:�"�4Mj#�/��(����g����j=�rnr����� 0� T%��sOA �A���^Tp]AAC�� �:7�p�b�n# ��iJ�fq}��D��j" U���*��� ����U�uU2��LC���a�
��4���P*���g�$�Gu0*����EgF�����* J������TV��*%�hQ����R�zR>�2����bW�HEUnE��
2���H<O>`<��j�b*'nqMC���4�{��n��`����K���$�5��z�;���,:�_LO���'���=��|`�x�z��������;] ��,/{"(���f$�O����������SX���?���E�?e��HR%�����)���Q�h71d�a�S$�f�T+HU�]���\����S����~�vA.�?�A�"�������}R-/[��k�:��!�S&����Tt�9J984T��[���?����T)��R��
I�HA_�jy��u�JF�T��WY�N����/�e��Xk�����b��nIQ2��jybuX�� �zw�����p'9���g����J�!��{������H��d��?�Dp�094t�?KX%��^UV��J��S{��_,��Z�����F(!����(�;���U�R�)e�[��R���F%�i�B���M z�� ���%�j��U�^E��������E����C,�G=�?�t@~xN�]��������X��3[��l
&}��A?����� z�-.��~�Y��.pV�}�r�)E��z}��*�*�/+�����}��O���d��{�_0!,����}��*WX���:fEgr���]��T��g)t��� �W�,N����R@}� ������k���`�|����&�` ��/xb������v���a�y��Y������h����a]�?�h���$�c�3�G���� h["T��]!8��{�?F5��Ak��f��@T�J&-,��������y�8]������"���+T$��e�� P����w�`��@�#��G�H���8>(MW������^[o�w�s���~
�*�����$��~�.�/��
".P�z�~�f [����k)a##����Q������D�,zA �z�~���BX�q���K �A�ZA� g�0��^����&\[����r-#
���1�z��k����� {t~���]:_����%�~����(��eu�N�|��Z�#�l~�LW��~z���u!�,�\�5*��0�T��k8�Ix�����B#�ai���7*��qV���_V��n$��,�h|�y��po��eL
�� ���%��-�c��z~<�JDh�5T_�E���]I����L��/}!�n%�U���K��~gm5��g�s�C���^�8Db����U�{�q%�B^u�*}�b���k
�{/)�xp��'��,�� �!"��q��=��j��[>T0!����W�{���AK��l��A��gN�~�F��8E|�V��{�_�^���Qq���������@0h�(Q=7*
�<�+*K��"
/��22����I�U��BMn�YZ���F�\t���)�Ce�e�#F^����C������-t�z������R�W�^2j��i�)�be�%I%$*`��7?�P��A]g�e����$��,��0�[�q��J�r� ��9�p��+y�}��3���qN�zL���Y�+� �k�����������e��q�q��V�^2���y���_����[��G��g�$��*�����E�%K�ZK/eQ��)��CH�b�
��o��J��B�<P p?��|�x����t^��T��V)����%E�YG����D��W)��]�6�W��������Q�)���]�q���2U���p���\E��
*zMe���=�V�:KZk��b�<�jz���iu�Y��>�l���/�h�3����:������N����)�=��9iF�,���O�k����5�;���e����G*;*���cQ�
�,�����1������TSQ�
W��^�_<'���`;�k��������T�i�����6��$�9��<���b_����p3��1]���� ur��?q�`�w��.�/��� \lI���+]������6��/�+�FW&\!�����D���D_�o��l�1�R�@*�/��^[} ���}�?��3�f��H��^�����A���3(���4�g��bp�p����$�v%j���ke�%���-����x� ����M]�_�I@�%@/��QC!��Z��Mv� ��3���x�d���x��/�7>��O��J ��
�L�� ���
���jK!�����o����������vvV068�C����X��� ��ky��Py�/�ILp=�?��>�ui���J�K\�>q��fA��{�,KrY���V�� ��jz��~������Z�"
WK�������I����$��@�p�G�Z<[i���fi�Z�n��ADp���y���_��#4��������?l���iZ��c5�}�CM���aW��
Y��y�v��$�8g`�!1lb
�7����U+��4>����}%IVb�����f�Z��R����B:��VR��
�a���u���lWV0��w�Y�����7���d'�����z|�5�7!=$#���f����RR��e�5�4�IV���"�m7� )��?x$�
-�-��B���:����?$%�8i�?���Xy �����y��jM�q�"GB�I~BO��n��Y��3����a��H��,Y�?�>�E�-������FV�s�����f���]�qW�� ������~B(��h���n��=�����A>����n�W��"!�����=b�`�����2&�%�:�?4� ,�oK��t���N�����&��yX�kkxB+���Y��CX�����Z�8�#����G0O�������=�y�J�("#Nj(��k�m�u���t�,C����5Y�fu�8!�:X�I����� +��+#|��C�2�g�e���=��\�����?��IY���)��j��mp����YV������'E��c?�:a���v������9��������%�����P�T�Vn�����E*�8�-��BS��=$J���DqBi�~���W�9R���>�[lAhGEEW��O��~����u����{�B~���F_D ��j'?4�x��%m����-�R�;�*�����bL�����"�������de����������`�zV�?����e�n|���5�J�K|��nF��������������+�����������@�)�k��% �6"���8�J*��>���������E �O��H_A[k��a��pG*&%['�Ge _�;�Z��K���� �tM�<)e��l�&0��b�2|'�K�k�����R�:S����T� ��|+��=�U����J����/�E�D|'��mp�D2��� �G�|gQ����+���t�����D��
�a`#��LE�H��M��{C���)W�1�� -�$~N��@.�Mi�rT���~m�t@��]h�k�� �� J�X
��
p?���|H-��/���Lm��RX��x/,H��' `����/ZZXY
p�t�P������Uz��v] g�� ��+)���X�
�����F�����`qC��Ui��!G��xq�/�f� ?&U�I2���l|��3#��9���� �L��%�X��1 ���40��P�A����i���a\������, �����Db"xp�]QK�b a�� 4Ys� N��2��������8a�H��u�[����Zr�zt�`�����h�
h�2o�� ����$�@<X���c��?�h�`��}tS��om���Ih��r:�?t����-��D�����wA�J�U���M��1���hl
��������R�nj�/�u���q��T�9�������NXH���l &A��~�n
���=�t���|� b��~�yC%��/��7�u�X"lsh��-��W�4�o���ztS)�
��j�=����������\H����l���U
q�lz=��M����%��"Q�'������+��=v�[�QY7�i����T.D�=��J,���&m�^98���7������J�\_���g�RL�+���`.�~T����K���v1�P[|�fHW������Y����_����[7��p�Bs�~H&�������6��-�M�b�����Mc�Z[����� ZL����q$� ���t��3�D��orN���R;���<b#�k��a
\!�c��Gt���]+��|9�='����S�Q����F��EbPS>��rEj�q9x�'���{��'QF��1j�]i}���R��Dg=<;+��a\�7��&#��%�{5�� B��&m�������|dC$p�:���p�s�Sk)��'?P�����64
V'�T�[7�b�d�RL'8��LXJ�5�p��\�p�D
;����2h���O��!%������d�����h��C�U������n8-m����7��2��yA�v;~S0������k�5�G�y����"|;|�l��&�D8���Qzt���R��_0�HsRL�9��L�����l��[;C���^B�H|�q�����T`�������t�5�-�1��{�"�6DrtSs��c�df���$��q���
DFo�>8iT~#�����jc�@�=qq�9� ��o� pAn= ��� b��F�������������
�����������(�{2f�������N�;K��-�t�rB����5�h �;��!TM��6f"�EJ���������h�������e��y�&+XB�����X�dm���J��g��[k4(Y/�[R�����^�����V�) ��s��V�P�`�#�gmH�_;�W g��=;�>�k!y�+G�� ��I#*�������l�P��J����8{�����+���� ��g%������,d��2c.��VR��>q\�E���O3F ��N�V�e�����o*�.2T�)@����eT|g,E]���E���!�����o����B�<$�"���
�Uz0�J?k�[���m�Jii���]�����^�[
k�����k��^����V>"������E����-�
�����F�r��-Hf���
+P���~��+�H�Q>�������
-8��h%��Y+����VKS�a)�O4�b#����6 H�{�9G1M��MQ�������,��*l�f������"��P��F�nz����/�e�k����u�S���]�����v�4�`���I���+<u=�)�gP���������X:���?���������p�{]Y����*~�@��� ��M#V��F�4�����*��e�t'I4��� ���Y���@6�0���W���Zb����w���]�WK�a����5�)-5�����?�F*���YV������<zk������I����a��M�z��=�����j��V���VL���O�V���������!�������������E�8��|���N��(#e�GW&���H�����Q�����?����1JyDT3���/��W��*����MQ��r����'��2�V��^x����
��3Uvju����!���y��Ox�&�h��c�_�\�����[������{4�����B��z�9j2����uI�$�����u��A���MM[g�A�tHZ���S:y��EG=!]�Q�p�%�uS_�(���@�vtS �����*|e�e@[u,�n��2�����N����MT ��C9�^���[�B��r�0�����e$�sS�����($�F��!���3w��
=:������i�N�^��y��m
�����������Q��]��5N.�b�B�]�nt9FO�B�u����l� ��+X���M���.W�.���G!MtL��v��L��{�H��U��
!���qtSX.{�������z����K����?���7����o�����$")�����W��NBw������p#`��tc�M��v�������8�Y ���a_iid�{�4�Az9�:{0%����4xW!A���v�&R]=������X��������|_�.h�N�����!�4��H�����o�(~��'����|k!GO��%�I�4�����$����v���;�H�����
���8o6g���[���u�������2\VZ���k������V���w��uDsc�I��o��m����Uo�������\~Q�W���]�k��m�w�?��������������Y�5��h�
a��k3���Q�����#��`�����ku��+��C��:n�VI��1W��z����QXM���O0�0�����T�����xBD����
I�=�� ��|g��'��O����-�!����Nc����nJ���[���8��s��w���(U����d��J�tB�
��oU����@�XR��#�:~�����y��!I��s�$P�.~�O�W�e����[Y�+�k�4.c����:�lA�B2�����=?[H��HZV��1J��g����aN�F��?�z��>����K�?x�S�(��F�@�2
�=�)�K�Y��oU+j� ��QG������P�<%���R�����p�+d�B������#a�E_:��#���>}��I_F!����b��}$���G'�[J��/s�r�R�$�HnV#�Y����s-z�s�V�o�j)�m���?mv�3�����v���o����1��*�6\��u-��j�����[5����G#3�!w�����c��|�
��������jW
�tN@��/�:dmw=�I�"5�d�FK��]#�� ���z��e���['�lvrw�$���p��1!�_�O�����������v���+6{?��2���M�Efy��D��_:�k���u~H@K4������N^l���
�c8�i4r���Q�V�]��#x�Q#���H����h��::�a�,��w��$�]��
B��4K8^Tx4�������J{�i������6�gc������w���k7:�N��`Sp92��1uP'������: E�����8���>Rd�omd_�m��k�{�J�t������?*a������*�v���������?<����4R�Y���8��
�������
UF.W�N��7MC���U/������;y�8wj���|k�]'�0���� ��M��C���kRL6�dX5����C��p/'����ztM�e:��Z:J���� ����&9������"8��%�un!�� �B.��i��+�]gk&��]��_7I7��������[��gZ�f���
`(��r��5�"�+�9�8���?!D���*=� $�vtSc�h�.5����d��H{>U�N��<�h��4C����!�l���NI��ka�0������� �����K�������?�H�%�CY ��i����HR(j��7)�0E�~�-��(t�'�W��prM&c����%$����+���
q�����%�M8�)| 0���zx��p0��zV�����:��B$�����++SpCB�����k�LG�w�^+���kU�W����������zd<;��+3���$K�-��f�i��]%G��d�'���?�Z�8�����&m�
���� o�$���'��������m�U `O���n���8}�����t����rJO��6��v68-��4�J+�.������
�!�s0���������O})W
f��_���EZ��Xd8�pa��#r&$�������o��#V�����#g:������Ze��B��:����W��[��U���N����2+���?�����{�R��s4��?�����]����;��������w���b������E�^��-T����'� Rh|i`$K P�pp�s�Y�QK�a�d9���n$F(���twp�PI����L��2���
���
�o86�D#S��O'H���Bqas[J��>�@��K+4O��vDn�+��1)86�����b��>u�� t.���
�X��$�h[4��)���E`;A��"I6��k�k(c��W=B�{6
��a�D�L��y�yN������O>� ��&����`x���Y[��83���]�,GH���u�8UY$@G���b��Ly�� ����@��zBB���Q���&^P��N�I#�2{T<4�H@6��T7c���?**�#F�BqmV�p�X��OH���"�A�o0�@�cpq�����V3~~H}�N��o�{KEqD8�f7�~�T��������� ���t��������Kp Lhe���k��\A��P���<�I�������\g:!@mI!y^�@�����J#M_����dG���7D�?��d��{
���Xmu5i�C�����H��`-������%��:�0�
� ��&��N�,Q@�N��N�>��J����g@�B��� x-P�#C
�Y0V��^Q���N+�������ltIg�_4�T����/J���E�)���vodh�j�S|�Ps_j3�Z���
�v!�hJ��\�}9�H�+BM���d�t6���Ek��/���c�#�z��jP��uE
�H{
��J\[��`�3V���N�"���b��}������QW�*�R8��fR��*U� "�/nSW�� d�U��F-B�@�x�A]�]-qr����L�����S�@���k�����Wc��w�k����b�-AEb��������"O�<�����v=�d!�S�f�nzc�9Z�M���]��A��E.f��6 �zcp�X,�� ��9*���>��8��8>���R�D��Be��]�
�o�S3S��
����"�+&�G�G_��T�^�/GC"������kg���$Pw���RjA��5�����.����r,AYH��������}{�J��n�B��7�@�D��+C���������6��L6H9m<������v|��3X��U�3)��=�(��[�:�9<T����U�{4Z%����+�'��A�-���� ��[�*�Y]�-�)��~����c�C
Y)���tv��
Z�Z�}e|��s��H���+���t�4�)����W�2��/L�U�+��k��Jw����@���c4��&5���f�q���hW�J���,�-0�-�|�}|���I>0_��w�H�*����r
G8
j2��aP"����P���t����2��p����d�H2T����D�q@�+���<��)��?���s�����`nR>�P#R��Y�8���q�C������U�d�d�~�H%�����E�HW^��p���,�.|G��$�F���n���:iJM�:}�t��
����&�'�8���g���UI���*��������Y���eq�/G�GePqyr�-�,t�&���-���o�x��7`�]]�A��eD�����H0� �{�.=X�_ �:
j?���
:��������C�������]�p��$ (��Y� ��V���x�bZ� �
��+��/u���������@��U�X��~z(��?f��UKA����e"�k�(�Eb�����`��F���A �3�6 ���f�� �J�?:�������������% ���i�k�wF67��n*8���c3J��A Lp��/��vf��Q6N�1�J��4�a�&n�0{32|_:b,j���h��KD�L@.�����$S��K��^�tq��
�Ed��B��>:�e�EZ=���Avmc ��� ��o�m��E����������l�4���PB�_+t��� GE���o.��YH���<d�BU�ktzM������2R���R���{���^ ��d�M9Z*��/�"tD�oJ���BiV"�< ��%1G�"[Q)�����h�lY����T+�0�}im? ��+W��� �rx���7O*#�k�-hT>��+��g��V
��:NV�7��@_�A �:"�.�C�~��6
������Q+W Hp��VX�*��G\��0�b�d�c ��"a�����l�J�U!b��=�hL�D�9�?�'�d8 7���]����>���2`�T�Yy�v�,0�p�[���������%Z*������]'$n��������QY�$��/nR� ���P��L�16@/O���K���K� 2p���V��e��O� .�0�$�^�����6
`���7��/F%^����g������
`��+J���8Gg���/ ���i�@�]�'��1Ct�P ���M2 ��oF��:/�������jM� ��j��������%�.�Y�p��G*�r��O�u���9��6<Ct:f�])��
x��k%���7���������f)���JK#��{G:I@�
:Y������)�D�x` �H� Whk�7'�`�gP��uV�0��p�����v����0��;<��T!Ur=^�"+z���{m9�_N� Vq�+��M� }[���q������5m�pT#O+�a��������|c~2��(��`�h����il
kJ+����W���J��` ���Lz�~�ce` H/�C�*��o���Ur�'�� ���H(�����FL�r��A^e�n��/9@�4t4��(��n}=�V�J�@�!�\
��P+]0����#E�@��c@���9���nz�S ������vR�*���0x�h���1���
��c��
�����-�@X�� ���$�j�#�H���,�:Z,�e1I� 5� ��cp(������]���Y$E�aJoi�#�Bf(;p�N�����k#>��p'����um�����a����I����J0�0�}w�}9x� ��a���>�t��k �sj�&Ie;+�$��a�s�Q=��8�;+O0� �� y�fPB�� ��7�XF�;$�8� �y9������qt �U�S��S�������od�t���*�~�Z��6�� � H���J4�����)].���
8�p��c�����b5J�u���V��~ �
����A��� |P6��b.kI "�9hm
1�L��`��u���U���.��S2D��n ��!vNsx��� ���!�r�X�2H��#lxB�fq������I1�����9�����������r�������6�������?��?zi��!5P<����]����������>]���)�$(T�����x?��X���Z(e\g� �-�*Fl�Z1�\;UmZ�@3�����.���T�D�=
����]�c�epa����97b.�J���6:8
� u8�v������w$#���P������Z������`��U� ��h�$%�����]���nlyH�����/j��k�!�U�a��i� 5��#��.� ���.r�m�d�*��Fnv��IT� ������q�h�_�Z��;��������Q�t���� �yQ7@�!k,��SA�A��;�!Uz Z��������"w
�w�7�Xm>�j@�?��W�����Q�DM[ s�2
����xU��/&����V��� ��x�{�
��fB`��!���� ���T�XLZoP��q�o�I�!�����C
f����� $��\M;�!$XeA�#w�%�8��Z4�97|�
�.G{5�����a����aFW(����E
���)4�� _��{�p;� ��PdA�@� <��V�,���Z���1� !:1����u'�S�Y�����P��l����7<�O.������h=2�o
6K�&�0R ��>��o
6�O1���Z���2����gT��1�
&�D �d���s�� ���[�2��\@I1Y@���1���'���=�N�B&���"��%�V����x_s������0K����k�J��[�������
��2`!#�G6N��j�����LP��( ���?{��t�3%
��#H�Vn�*�����X47��i ����)=*^{����@� ��S�����8$vc.*���"�x9��I��RC|�����r��(�������)w�\�h� ����
p[�5����A6��Po*Y�zjB�P��>�6�����H��8��?��)K"V&�$%
�����f�G���G����������6���{^:L�I��3���Z:�3��c����u�?g�gGk�@=`�5��l��6N���@�8M,~$J�< �8�8� 4 �S.#�3��{E�S2Fy^E���a������s��= m W�� �����u�-��F��s\�ef�7tX2
!A`J�6|���x�`����E�>2 �{���Fu ��c�l�!�l�:b&�s�|���`�CRSF5���q���8������[������tL���h�k� |��
�O,�"����'am��w{�{&�9��j:����w;��4NE
HUX���IQB���B ��u��+������C���� ��F��~�n��'�(����C(7���"�F���H�����6���5�Z=p�2������By�Ny�u/�lc��"��P�Q�p>Z1_)�{J�(pQ��|�Q8I�$yR�B� ���aBt�a�����a�G+�BN�vtXG�����=�e���������������b@'t�XU,��i� �.�`�E��J.�so�gG3^�Xp�f��H����qC�jef����J-�
p��������e;y����u�(�8(�
.p�Fv�gA �a -E��{W����[6��m��bT�PpMZ�Wu��$���~x��`v�r���%�B'ca�s1-C�P�zqMRFk���u����'�9�+�?��U�=������cp�O�d$��1����m���@<����$��+�yBB�?J2`����?&��hb��Q.|.���������������|�?���U*eD��3����cQ* �d/c�Z��@�y78-2%w�@{
�� �1�H�c9-
��U2 H������8f[��'����J1��� ��0}�a�
���Fl���;�0�W������y^���+������;#���m5�x�l��
���!�q��C����E�'���u�R�4�`���r���8�b��NpP��0�m��"��F z��� �a �9qoC��3�D��W%���\Q��Ld�P$?��J�/�z�nx����F��aL�
ed�CR��k~(�F�����G�[A]R ;��:����&D�{�[c��Y�q�������
>U����&Y#��0E��t'���x#(���P�R
�D���'��Z�R�L��[iy0�!0y�T������Z�s�:�h�6@����C��+G��#�{���FVN����*A��R��F�/�R�E��U}j.�-�?�n����M��p��aQ=Z��p7�_��&��@� f�������0��&1��q i�5 �ZP� ����)��#�-1=z(F��F�F���p��rC�b,����BXN4�1�����@+���h�?��T� RBE0������@����-�
�Q_1)�>��Q&�b��_��J^�E]
g�h���>a�QPiC<~vC��O�5����z���k$�"3�p�o������l��
f\Qj��CF$����#��<vI�S&�S�:�����2��5kL�W/CK�* 1����
��@�K/�P:+�]E�BI�Z����js�Le\�n�w�L�T^K��� ��8�^�~h�KnJ�u��[�)�C���;�C�0�|��iq�CA���X9��e��V��\c�}
���B������1x��`��`��~��bGZ�7c�0��`Y��F�J)~���eJZ�!5vP�MW*im��\���G[q�qx�m��(��b
Ya�T�\���B}~�l���
��P�����8����8=�Rh���}��<q��
u��#��nL�c��>�1��.��jLn���
S�T`��c��:���v��k����� �/�8&9��2Gp�*B��Xr+�(��hIl�91|C}��70�����M�@���}����FN�<�)
���A}��PI�2��A��V��05@�������d6�cF�N�O��*P��-���E0�P��#���>�M��b���t^cPg�����O���E �C��?p�1l} =�����HR�t��^�L1�^B),b8(0G�'o��v���]�C��b>��T���P���z���>
���3�Y�)��F��y����u5I1�GAF�
��_����:���U��{@r��6D����' ��%�|�{�d�(/�1�5�|Hp�C9^A�D!Nv�����B���`,D�Fv������?:(&`�A|�Z�5� �b�g�C�u1&&�[F�����t�_�I/�P )�������P(U�X�>��h�h`�1�w����pY!�xuhb�le�I��3k%��+�"��
�����S��m]�A|XE�/���$��md�L _9?e�UR��
�I��nL����|�I�
`N�2�2m�U��d�[���v����d0H�� �h�A��{��a��kA�)���=j]@1h��B�'F:������S�#ZS4C{�y�s�����k�:��C=G�|��x��q��K��C���J�W]���0n�4��h�����%F<$`�`.�$� �������O��Ec�������X��N��o���_�Y����?��}�?�g�?�YpP�G�����[���ua*��`/��,�����}`�������C�q�P��������p���I��^�$��C��Up-Cu�.hK�=N�����o���� i�A��?�����*Q/���B��k��`m
}=a�'&/�E�f��pQt_�L���J�����t�r����\S5�f����h�C+���D�#�}���t"GGD�XD��/��}���d���"�x�>[��?����o�T���I��F����6������?Z�J`N�E_��'{(�]2�G[��p��
��1mK���D���5���� ���2AmH �o����r.�K�A�����:"G��A�A$t���
K� ;L |�=�3��k�8�y�O�-����]Cv^�6�t�4�gi�?��G]�\Iuu�D��V@���yRV;4� L�Sm� -�o�����F:n�G�XK�=��#���hc?j �
�Z,��(��`�=������'��Dh���� �A��A��EE[3���]j�3��`���O�U���7KDM��(���!@�e����@�,I��H$������������bB0���!��a jp#�?R��{���J�MTJ�x�t@��5 �
h��3�oHSLu'�U������a@��jd��Es� ��a@.l�P�
*p]�+Z��k"���8�IJ<