Building a Dict with 5-tuple keys is slow on 0.3 and 0.4 #11100
Comments
|
related to #10208 |
|
Its worth noting (maybe) that changing it to So the GC is no longer doing as much, and the times are better, but more memory is allocated. |
|
|
Good news: for those who may be familiar with the |
|
I'm probably misunderstanding something, but didn't the performance tips talk about operation in column major order being much faster? Sent from my iPhone
|
|
@ScottPJones unless I'm missing something, the example code only has Vectors and Dicts, so that advice isn't relevant (you need two dimensions to have both "rows" and "columns".) |
|
@pao Thanks for clarifying that... I had suspected I must be missing something! |
|
@JeffBezanson Just curious, what constitutes a significant addition to the system image size? [Again, just asking, no criticism implied or intended!!!] |
In the real use case we are generating the code with a macro and don't actually know that its a tuple of Ints. This is the
I can check, if its still useful? |
|
@ScottPJones I think the increase is a couple hundred kb. |
|
OK I re-wrote the benchmark to make it more clear: using Compat
function count_mem(layer_verts, adj_list, num_layers)
var_count = 0
for L=1:num_layers
for i=layer_verts[L]
for j=adj_list[i]
for k=layer_verts[L]
for l=adj_list[k]
var_count += 1
end
end
end
end
end
return var_count
end
function bench_fulltuple(layer_verts, adj_list, num_layers, var_count)
c = Dict{NTuple{5,Int},Int}()
sizehint!(c, var_count*2)
@time for L = 1:num_layers
for i = layer_verts[L]
for j = adj_list[i]
for k = layer_verts[L]
for l = adj_list[k]
c[L,i,j,k,l] = L*i*j*k*l
end
end
end
end
end
nothing
end
function bench_partialtuple(layer_verts, adj_list, num_layers, var_count)
c = Dict{NTuple{5},Int}()
sizehint!(c, var_count*2)
@time for L = 1:num_layers
for i = layer_verts[L]
for j = adj_list[i]
for k = layer_verts[L]
for l = adj_list[k]
c[L,i,j,k,l] = L*i*j*k*l
end
end
end
end
end
nothing
end
immutable MyKey
a::Int
b::Int
c::Int
d::Int
e::Int
end
function bench_immutable(layer_verts, adj_list, num_layers, var_count)
c = Dict{MyKey,Int}()
sizehint!(c, var_count*2)
@time for L = 1:num_layers
for i = layer_verts[L]
for j = adj_list[i]
for k = layer_verts[L]
for l = adj_list[k]
c[MyKey(L,i,j,k,l)] = L*i*j*k*l
end
end
end
end
end
nothing
end
# Create data
layer_verts = @compat Dict(2=>[4,11,21,24,27,29,43,55,56,58,64,66,79,81,100,103,105,110,115,117,119,120,122,123,126,128,138,147,155,178,179,180,185,197,215,227,236,244,250,257,265,268,277,278,281,301,302,313,314,318,323,330,344,349,353,371,372,375,389,394,397,403,418,420,429,445,450,451,456,457,465,505,507,516,519,522,549,553,558,574,577,578,583,584,596,597,600,607,608,609,610,611,612,616,617,620,623,624,625,626,627,628,629,634,639,640,641,642,643,644,645,646,647,648,655,656,657,658,659,660,661,662,663,664,666,667,668,669,670,671,672,673,674,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,698,699,700,701,702,703,706,707,708,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,732,742,746,747,748,749,754,755,756,757,761,766,770,771,772,773,774,775,776,777,780,781,782,783,784,787,792,793,794,798,801,802,803,804,805,806,807,808,809,811,812,813,814,815,820,821,822,823,824,825,826,831,832,833,834,837,838,839,840,841,842,845,846,847,849,850,851,853,854,855,856,862,867,868,869,884,885,886,887,891,892,893,894,895,896,897,903,904,905,906,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,941,942,943,944,945,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,968,970,971,972,973,975,983,984,989,990,991,992,993,994,995,996,999,1000,1002,1003,1004,1005,1009,1011,1012,1013,1014,1015,1016,1017,1018,1019,1020,1021,1022,1023,1024,1026,1027,1028,1029,1030,1031,1032,1033,1034,1040,1041,1043,1045,1050,1051,1052,1053,1054,1058,1059,1060,1061,1062,1063,1064,1065,1066,1067,1068,1069,1070,1071,1074,1075,1076,1077,1078,1079,1080,1081,1082,1083,1084,1085,1090,1091,1092,1093,1094,1095,1096,1097,1103,1105,1110,1111,1112,1113,1114,1119,1121,1122,1124,1125,1126,1127,1128,1129,1130,1131,1138,1139,1140,1141,1142,1143,1144,1145,1146,1147,1148,1149,1150,1151,1152,1153,1154,1155,1156,1157,1158,1159,1160,1161,1162,1163,1165,1166,1167,1168,1169,1170,1171,1172,1173,1174,1175,1176,1180,1183,1185,1194,1195,1196,1197,1198,1199,1200,1209,1210,1211,1212,1213,1214,1215,1216,1217,1218,1219,1220,1221,1222,1223,1224,1225,1226,1227,1228,1229,1232,1233,1234,1235,1238,1239,1241,1242,1243,1245,1246,1247,1248,1249,1250,1251,1255,1256,1257,1258,1259,1260,1261,1262,1263,1264,1265,1266,1267,1268,1269,1270,1271,1272,1273,1275,1276,1278,1279,1280,1281,1282,1283,1287,1288,1289,1290,1291,1292,1293,1294,1295,1296,1300,1301,1302,1303,1304,1305,1306],11=>[158],7=>[46,104,165,246,291,317,411,483,512,704,874,875,939,940,1046,1047,1469,1524,1525,1626,1682,1683,1711,1757,1767,1768,1810,1906,1908,1909,1947,1951,1952,1972,2006,2007,2025,2128,2130,2148,2162,2212,2224,2263,2264,2323,2345,2433,2437,2441,2446,2461,2462,2470,2474,2518,2519,2576,2578,2610,2611,2616,2641,2665,2666,2669,2670,2672,2681,2684,2685,2686,2694,2704,2706,2709,2710,2711,2712,2713,2714,2715,2719,2720,2724,2727,2740,2751,2756,2760,2763,2773,2776,2780,2792,2801,2803,2812,2817,2818,2828,2829,2830,2842,2843,2862,2874,2875,2881,2884,2885,2888,2893,2894,2895,2897,2899,2900,2904,2905,2906,2907,2909,2910,2912,2914,2916,2919,2927,2928,2931,2932,2933,2936,2939,2940,2944,2945,2947,2949,2950,2951,2952,2953,2954,2955,2956,2960,2965,2966,2968,2969,2970,2971,2973,2975,2978,2979,2982,2983,2984,2987,2988,2989,2990,2994,2995,2996,2997,2998,2999,3001,3002,3008,3009,3011,3015,3016,3017,3018,3019,3020,3022,3026,3027,3029,3030,3031,3032,3033,3034,3035,3036,3038,3039,3040,3041,3042,3043,3044,3045,3048,3050,3051,3053,3054],9=>[562,1341,1541,1607,1772,1946,2062,2063,2105,2170,2432,2465,2466,2526,2556,2575,2597,2604,2628,2677,2697,2700,2707,2725,2733,2779,2791,2799,2819,2826,2840,2877,2889,2938,2941,2943,2946,2957,2958,2962,2963,2980,2981,3006,3007,3025,3028,3057,3060,3061,3066,3069,3078,3080,3082,3083,3084,3085,3086,3089,3093,3095,3105,3117,3120,3123,3128,3130,3142,3143,3150,3153,3159,3160,3167,3168,3181,3190,3191,3195,3198,3199,3203,3204,3205,3207,3209,3210,3211,3212,3213,3214,3215,3217,3224,3226,3227,3229,3231,3232,3233,3235,3236,3237,3238,3239,3240,3241,3242,3243,3246,3248,3249,3251,3253,3254,3255,3256,3257,3260,3261,3262,3264,3265,3267,3268,3270,3271,3272,3273,3276,3277,3278,3279,3280,3281,3282,3284,3285,3286,3287,3288,3289,3290,3293,3295],10=>[189,272,1244,1907,2068,2125,2265,2389,2471,2472,2497,2728,2752,2753,2788,2808,2820,2835,2839,2859,2896,2911,2913,2918,2935,2942,2976,2985,2991,3005,3010,3021,3049,3059,3096,3099,3100,3103,3114,3115,3118,3119,3134,3154,3155,3169,3172,3200,3201,3202,3206,3208,3216,3218,3219,3220,3221,3222,3223,3225,3228,3230,3234,3244,3245,3247,3250,3252,3258,3259,3263,3266,3269,3274,3275,3283,3291,3292,3294,3296,3297,3298,3299,3300,3301,3302,3303,3304,3305,3306,3307,3308,3309,3310,3311,3312,3313,3314,3315,3316,3317,3318,3319,3320,3321,3322,3323,3324,3325,3326,3327,3328,3329,3330,3331,3332,3333,3334,3335,3336,3337,3338,3339,3340,3341,3342,3343,3344,3345,3346,3347,3348,3349,3350,3351,3352,3353,3354,3355],8=>[434,651,883,969,1184,1388,1533,1534,1582,1583,1660,1661,2012,2056,2057,2144,2187,2188,2213,2251,2260,2261,2291,2359,2360,2361,2390,2393,2394,2404,2428,2429,2439,2513,2514,2529,2540,2574,2582,2605,2606,2652,2668,2729,2732,2734,2738,2749,2750,2757,2758,2783,2784,2821,2823,2844,2845,2849,2869,2886,2887,2890,2891,2892,2898,2901,2902,2903,2908,2915,2917,2920,2921,2922,2923,2924,2925,2926,2929,2930,2934,2937,2948,2959,2961,2964,2967,2972,2974,2977,2986,2992,2993,3000,3003,3004,3012,3013,3014,3023,3024,3037,3046,3047,3052,3055,3056,3058,3062,3063,3064,3065,3067,3068,3070,3071,3072,3073,3074,3075,3076,3077,3079,3081,3087,3088,3090,3091,3092,3094,3097,3098,3101,3102,3104,3106,3107,3108,3109,3110,3111,3112,3113,3116,3121,3122,3124,3125,3126,3127,3129,3131,3132,3133,3135,3136,3137,3138,3139,3140,3141,3144,3145,3146,3147,3148,3149,3151,3152,3156,3157,3158,3161,3162,3163,3164,3165,3166,3170,3171,3173,3174,3175,3176,3177,3178,3179,3180,3182,3183,3184,3185,3186,3187,3188,3189,3192,3193,3194,3196,3197],6=>[86,242,243,249,295,367,377,386,517,520,572,799,864,865,866,997,998,1072,1073,1106,1164,1177,1178,1179,1231,1237,1340,1342,1343,1389,1393,1394,1395,1396,1420,1460,1461,1462,1483,1610,1612,1632,1648,1710,1724,1770,1771,1856,1857,1885,2013,2019,2027,2028,2034,2035,2051,2052,2053,2061,2067,2135,2136,2137,2214,2215,2219,2220,2270,2271,2276,2277,2306,2341,2342,2343,2348,2349,2351,2352,2366,2372,2373,2374,2385,2400,2402,2403,2406,2407,2408,2409,2411,2412,2413,2414,2415,2421,2422,2426,2431,2440,2449,2450,2464,2469,2473,2478,2482,2483,2501,2502,2503,2504,2510,2515,2530,2544,2547,2564,2565,2566,2572,2573,2580,2584,2585,2586,2608,2609,2632,2647,2648,2658,2662,2663,2664,2667,2671,2673,2674,2675,2676,2678,2679,2680,2682,2683,2687,2688,2689,2690,2691,2692,2693,2695,2696,2698,2699,2701,2702,2703,2705,2708,2716,2717,2718,2721,2722,2723,2726,2730,2731,2735,2736,2737,2739,2741,2742,2743,2744,2745,2746,2747,2748,2754,2755,2759,2761,2762,2764,2765,2766,2767,2768,2769,2770,2771,2772,2774,2775,2777,2778,2781,2782,2785,2786,2787,2789,2790,2793,2794,2795,2796,2797,2798,2800,2802,2804,2805,2806,2807,2809,2810,2811,2813,2814,2815,2816,2822,2824,2825,2827,2831,2832,2833,2834,2836,2837,2838,2841,2846,2847,2848,2850,2851,2852,2853,2854,2855,2856,2857,2858,2860,2861,2863,2864,2865,2866,2867,2868,2870,2871,2872,2873,2876,2878,2879,2880,2882,2883],4=>[22,44,47,88,90,106,143,150,151,177,214,307,324,327,329,348,363,382,421,432,454,503,523,555,582,586,589,615,621,622,800,810,818,819,827,828,829,830,843,844,848,857,858,859,860,861,871,872,873,882,985,986,987,988,1107,1108,1109,1115,1116,1117,1118,1190,1191,1192,1193,1201,1202,1203,1204,1205,1206,1207,1208,1252,1253,1254,1312,1313,1314,1315,1322,1323,1324,1325,1327,1328,1329,1330,1353,1362,1363,1364,1365,1380,1381,1410,1412,1413,1414,1415,1416,1417,1418,1419,1422,1423,1424,1428,1429,1430,1434,1435,1436,1437,1438,1439,1440,1441,1442,1451,1452,1457,1458,1466,1467,1468,1484,1499,1500,1513,1523,1529,1535,1536,1537,1538,1539,1546,1547,1553,1554,1555,1558,1589,1590,1591,1592,1605,1613,1614,1633,1634,1656,1657,1662,1663,1667,1668,1695,1696,1697,1706,1707,1708,1709,1722,1731,1732,1733,1734,1735,1774,1775,1776,1815,1846,1849,1868,1869,1876,1877,1878,1879,1884,1886,1887,1888,1893,1897,1898,1899,1900,1901,1902,1903,1904,1905,1910,1911,1912,1913,1914,1915,1917,1918,1919,1920,1921,1922,1923,1928,1929,1930,1931,1932,1933,1934,1935,1936,1937,1938,1941,1942,1943,1944,1945,1948,1949,1950,1953,1954,1955,1956,1957,1958,1959,1960,1961,1962,1963,1965,1973,1977,1981,1982,1989,1990,1991,1992,1993,1994,1995,1996,1999,2000,2001,2002,2005,2008,2009,2014,2015,2016,2017,2018,2020,2021,2022,2023,2024,2029,2030,2031,2032,2033,2036,2037,2040,2041,2042,2043,2044,2045,2046,2047,2048,2049,2050,2054,2058,2059,2069,2070,2071,2072,2075,2076,2077,2078,2079,2083,2084,2086,2087,2088,2089,2090,2091,2092,2093,2094,2095,2096,2097,2098,2099,2100,2101,2102,2103,2104,2106,2107,2108,2109,2114,2115,2116,2117,2118,2119,2120,2121,2122,2124,2126,2127,2129,2133,2134,2138,2139,2140,2141,2142,2143,2145,2146,2147,2151,2152,2153,2154,2155,2156,2157,2158,2159,2160,2161,2163,2164,2165,2166,2168,2169,2171,2172,2173,2176,2177,2178,2179,2180,2181,2182,2183,2184,2185,2186,2189,2190,2191,2192,2193,2194,2195,2196,2197,2198,2202,2203,2204,2205,2206,2207,2216,2217,2218,2221,2223,2225,2226,2227,2228,2229,2235,2236,2237,2238,2239,2240,2241,2242,2243,2244,2245,2246,2247,2248,2249,2250,2252,2253,2254,2255,2256,2257,2258,2259,2262,2266,2272,2273,2274,2275,2278,2279,2280,2281,2282,2283,2284,2285,2286,2287,2288,2289,2290,2292,2293,2294,2296,2297,2298,2299,2300,2301,2302,2303,2304,2305,2307,2308,2309,2310,2311,2312,2313,2314,2315,2317,2319,2320,2321,2322,2324,2325,2326,2327,2328,2329,2330,2333,2334,2335,2336,2337],3=>[5,6,12,14,60,159,164,171,173,182,192,205,207,210,222,225,239,241,245,312,333,338,358,378,438,447,510,515,524,530,566,613,614,618,619,630,631,632,633,635,636,637,638,665,675,676,677,678,696,697,731,733,734,735,736,737,738,739,740,743,744,745,750,751,752,753,758,759,760,762,763,764,765,767,768,769,778,779,785,786,795,796,797,817,835,836,852,863,870,876,877,878,879,880,881,888,889,890,898,899,900,901,902,907,946,947,948,949,965,966,967,980,981,982,1001,1007,1008,1010,1035,1036,1037,1038,1039,1042,1048,1049,1055,1056,1057,1086,1087,1088,1089,1098,1099,1100,1101,1102,1120,1132,1133,1134,1135,1136,1137,1186,1187,1188,1230,1236,1240,1274,1277,1297,1298,1299,1307,1308,1309,1310,1311,1316,1318,1319,1320,1321,1326,1331,1332,1333,1334,1335,1336,1337,1338,1339,1344,1345,1346,1347,1348,1349,1350,1351,1352,1354,1355,1356,1357,1358,1359,1360,1361,1366,1367,1368,1369,1370,1371,1372,1373,1374,1375,1376,1377,1378,1379,1382,1383,1384,1385,1386,1387,1390,1391,1392,1397,1398,1399,1400,1401,1402,1403,1404,1405,1406,1407,1408,1409,1411,1421,1425,1426,1427,1431,1432,1433,1443,1444,1445,1446,1447,1448,1449,1450,1453,1454,1455,1456,1459,1463,1464,1465,1471,1472,1473,1474,1475,1476,1478,1479,1480,1481,1482,1487,1488,1489,1490,1491,1492,1496,1497,1498,1501,1502,1503,1504,1506,1507,1508,1510,1511,1512,1514,1515,1516,1517,1522,1526,1527,1528,1542,1543,1544,1545,1548,1549,1550,1551,1552,1556,1557,1559,1560,1561,1562,1563,1564,1565,1566,1567,1568,1569,1570,1571,1572,1573,1574,1575,1576,1577,1578,1579,1580,1581,1584,1585,1586,1587,1588,1593,1594,1595,1596,1597,1598,1599,1600,1601,1602,1603,1604,1606,1608,1609,1611,1615,1616,1620,1621,1622,1623,1624,1625,1627,1628,1629,1630,1631,1635,1636,1637,1638,1639,1640,1641,1642,1643,1644,1645,1646,1647,1649,1650,1651,1652,1653,1654,1655,1658,1659,1664,1665,1666,1669,1670,1671,1672,1673,1674,1675,1676,1677,1678,1679,1680,1681,1684,1685,1686,1687,1688,1689,1690,1691,1692,1693,1694,1698,1699,1700,1701,1702,1703,1704,1705,1715,1716,1717,1721,1723,1725,1726,1727,1728,1729,1730,1736,1737,1738,1739,1740,1741,1742,1743,1744,1745,1746,1747,1748,1749,1750,1751,1752,1753,1754,1755,1756,1758,1759,1760,1761,1762,1763,1764,1765,1766,1769,1773,1781,1782,1783,1784,1785,1786,1792,1793,1794,1795,1796,1797,1798,1799,1800,1801,1802,1803,1804,1805,1806,1807,1808,1809,1811,1812,1813,1814,1816,1817,1818,1819,1820,1821,1822,1823,1824,1825,1826,1830,1831,1832,1833,1834,1835,1836,1837,1838,1839,1840,1841,1842,1843,1844,1845,1847,1848,1850,1851,1852,1853,1854,1855,1858,1859,1860,1861,1862,1863,1864,1865,1866,1867,1870,1871,1872,1873,1874,1875],5=>[18,129,157,198,228,229,259,334,342,410,437,489,498,550,554,601,649,650,652,653,654,705,709,710,711,712,713,714,741,788,789,790,791,816,974,976,977,978,979,1006,1025,1044,1104,1123,1181,1182,1189,1284,1285,1286,1317,1470,1477,1485,1486,1493,1494,1495,1505,1509,1518,1519,1520,1521,1530,1531,1532,1540,1617,1618,1619,1712,1713,1714,1718,1719,1720,1777,1778,1779,1780,1787,1788,1789,1790,1791,1827,1828,1829,1880,1881,1882,1883,1889,1890,1891,1892,1894,1895,1896,1916,1924,1925,1926,1927,1939,1940,1964,1966,1967,1968,1969,1970,1971,1974,1975,1976,1978,1979,1980,1983,1984,1985,1986,1987,1988,1997,1998,2003,2004,2010,2011,2026,2038,2039,2055,2060,2064,2065,2066,2073,2074,2080,2081,2082,2085,2110,2111,2112,2113,2123,2131,2132,2149,2150,2167,2174,2175,2199,2200,2201,2208,2209,2210,2211,2222,2230,2231,2232,2233,2234,2267,2268,2269,2295,2316,2318,2331,2332,2338,2339,2340,2344,2346,2347,2350,2353,2354,2355,2356,2357,2358,2362,2363,2364,2365,2367,2368,2369,2370,2371,2375,2376,2377,2378,2379,2380,2381,2382,2383,2384,2386,2387,2388,2391,2392,2395,2396,2397,2398,2399,2401,2405,2410,2416,2417,2418,2419,2420,2423,2424,2425,2427,2430,2434,2435,2436,2438,2442,2443,2444,2445,2447,2448,2451,2452,2453,2454,2455,2456,2457,2458,2459,2460,2463,2467,2468,2475,2476,2477,2479,2480,2481,2484,2485,2486,2487,2488,2489,2490,2491,2492,2493,2494,2495,2496,2498,2499,2500,2505,2506,2507,2508,2509,2511,2512,2516,2517,2520,2521,2522,2523,2524,2525,2527,2528,2531,2532,2533,2534,2535,2536,2537,2538,2539,2541,2542,2543,2545,2546,2548,2549,2550,2551,2552,2553,2554,2555,2557,2558,2559,2560,2561,2562,2563,2567,2568,2569,2570,2571,2577,2579,2581,2583,2587,2588,2589,2590,2591,2592,2593,2594,2595,2596,2598,2599,2600,2601,2602,2603,2607,2612,2613,2614,2615,2617,2618,2619,2620,2621,2622,2623,2624,2625,2626,2627,2629,2630,2631,2633,2634,2635,2636,2637,2638,2639,2640,2642,2643,2644,2645,2646,2649,2650,2651,2653,2654,2655,2656,2657,2659,2660,2661],1=>[1,2,3,7,8,9,10,13,15,16,17,19,20,23,25,26,28,30,31,32,33,34,35,36,37,38,39,40,41,42,45,48,49,50,51,52,53,54,57,59,61,62,63,65,67,68,69,70,71,72,73,74,75,76,77,78,80,82,83,84,85,87,89,91,92,93,94,95,96,97,98,99,101,102,107,108,109,111,112,113,114,116,118,121,124,125,127,130,131,132,133,134,135,136,137,139,140,141,142,144,145,146,148,149,152,153,154,156,160,161,162,163,166,167,168,169,170,172,174,175,176,181,183,184,186,187,188,190,191,193,194,195,196,199,200,201,202,203,204,206,208,209,211,212,213,216,217,218,219,220,221,223,224,226,230,231,232,233,234,235,237,238,240,247,248,251,252,253,254,255,256,258,260,261,262,263,264,266,267,269,270,271,273,274,275,276,279,280,282,283,284,285,286,287,288,289,290,292,293,294,296,297,298,299,300,303,304,305,306,308,309,310,311,315,316,319,320,321,322,325,326,328,331,332,335,336,337,339,340,341,343,345,346,347,350,351,352,354,355,356,357,359,360,361,362,364,365,366,368,369,370,373,374,376,379,380,381,383,384,385,387,388,390,391,392,393,395,396,398,399,400,401,402,404,405,406,407,408,409,412,413,414,415,416,417,419,422,423,424,425,426,427,428,430,431,433,435,436,439,440,441,442,443,444,446,448,449,452,453,455,458,459,460,461,462,463,464,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,484,485,486,487,488,490,491,492,493,494,495,496,497,499,500,501,502,504,506,508,509,511,513,514,518,521,525,526,527,528,529,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,551,552,556,557,559,560,561,563,564,565,567,568,569,570,571,573,575,576,579,580,581,585,587,588,590,591,592,593,594,595,598,599,602,603,604,605,606])
adj_list = Vector{Int}[[607,608],[],[609,610,611,612],[613,614],[],[615,329],[],[],[616,250,617,456],[],[618,619],[],[620],[621,622],[623,624],[625,626,627,628],[],[],[629],[],[630,631,632,633],[],[66],[239],[],[634],[635,636,637],[],[638],[639],[],[640],[641,642,505],[301],[349,643,644],[645],[],[],[],[56,646,507],[647,648],[],[],[649,650],[],[651],[652,410,653,654],[655,553,115,656,657,658],[516],[659],[660,661],[574],[662,663],[664],[],[665,164],[666,667],[],[668],[],[669,670],[671,672,673,79,674,119],[],[675,676],[],[677,678],[679,680,681],[682,683,684,11],[685,371,686,687],[],[138,688],[689,690,244],[],[691],[],[596],[692,693],[694,695],[696],[],[697],[],[29,698,519,699,700,549],[701,702],[703,227],[483,704],[],[705],[706,707,21,265,708],[709,710,711,712,259,713,714],[715,716,717],[718,103,719,375,720,122],[],[721,722,723,724,725],[],[],[726,727,465,728,115,729],[730],[],[731],[],[250,732,456],[733,358,734,735,736],[],[737,738,739,740],[741,334],[],[110],[742],[743,744,745],[],[746,519],[747],[748,749],[750,751,752,753],[754,281,105,755,756,375,757],[758],[],[759,760,210],[510],[761],[762,763,764],[765,159],[],[],[],[766],[767,768,769],[],[770,244],[],[771,772],[],[115],[773,774,775,776,777],[],[],[778,779],[],[780],[],[781],[],[],[782],[783,784],[60,785,786],[787],[],[],[788,498,789,790,791],[792],[793],[794],[795,241,796,797],[798,250,155],[799,242],[],[800],[],[801,451],[147],[180,802,803,115,465,804],[],[434],[805],[806],[807,808,178],[],[809],[307],[58],[810,143,150],[811],[812,813],[814,815,29],[816,198],[205],[],[358,817],[],[818,819],[],[394],[515],[820,821,822,823],[],[824],[158],[397,825],[826,577],[827,828,829,830],[],[],[],[831,832,833,257,834,323],[524,835,836],[],[837,838,839,840],[],[841],[420],[268],[842],[843,327,47,844],[516,845],[],[450],[846,847],[848],[849],[850,851],[],[18],[852],[853,854],[],[147],[],[855],[856],[857],[],[],[22,858,90,421,106,382,859,860,589,861],[862],[863],[864,517,865],[866],[867,257,558,868],[268],[],[],[869],[],[5,870],[],[],[871],[],[872,873],[874],[875,46,104],[876,877,878,879,530,14,880,881],[348,882],[883],[884,885,886],[21,887],[],[241,888,889,890],[],[],[180,27,891,892,893,894],[895],[301,896],[897],[898,899,900,901,447,902],[],[520],[903,904,905],[906,100],[],[],[],[],[],[66],[],[],[],[],[158],[],[],[],[],[60,12,907],[173],[],[],[],[584,908,909,910],[911],[912,913,914,915,916,596,917],[918,919],[105,920],[921,922],[923],[924,925,926,927],[928,929,257,930,931],[],[932,933,197,934,250],[935,457,215,318,936,250,519],[937,938],[939,246,940],[941],[942],[],[943,944,115,180,945],[],[946,333,245,947],[378,948,949],[],[],[950,951,952,953,954,522],[302,955,956,957,43],[],[958,959,960,961],[962,963],[964],[],[],[965,225,207,966],[967],[968],[],[969],[],[970,971],[972,128],[],[250,973],[],[],[],[420,330],[601,974],[975,105,180],[437,976,489,229,977,978,979],[980,981,982],[],[983,984],[985,327,986,47,454,987,988],[],[989,990,991,992],[],[993],[432],[],[],[994,995,996],[997,377,86,998],[999,1000,389],[566,1001],[1002,1003],[],[1004,1005],[1006],[1007,1008],[],[],[1009],[312,1010],[1011],[],[1012,1013,1014],[1015],[],[1016,1017,1018],[],[1019,1020,1021],[1022,1023,1024,11],[1025],[1026,1027,578],[1028,1029,1030,1031,1032],[],[],[1033],[236,1034],[],[1035,6],[207,1036,1037,1038,225,1039],[1040,1041],[],[1042],[1043],[483],[44],[],[445],[],[1044],[],[1045],[],[1046,165,512,291,1047],[24,265],[],[1048,333,1049],[1050],[1051],[1052,1053],[583],[],[],[1054],[1055,1056,1057],[],[],[],[353,1058,1059,1060],[1061,1062],[],[],[],[1063,1064,180,1065,138],[1066,1067,1068,1069,1070],[],[1071],[1072,1073,295,386],[],[1074,1075,1076,180,1077],[],[1078],[1079,117,1080,278],[1081,1082,103,1083],[1084,277],[],[1085],[1086,192,1087,1088,1089],[],[1090,103,1091,1092],[55],[],[1093,1094,1095,1096,1097],[456,123],[],[],[1098,1099,1100,1101,1102],[1103],[],[1104],[],[562],[],[1105,100],[86,1106,572],[1107,1108,1109],[],[1110,1111],[],[1112,1113],[1114],[197,180],[],[519],[1115,1116,582,151,1117,1118],[1119],[],[],[1120],[1121],[1122],[1123],[1124,1125,1126,147,1127,197,1128,1129,1130,1131],[1132,1133,1134,222,438],[1135,1136,1137],[],[],[1138],[1139],[],[1140,1141],[],[],[],[1142],[1143,1144],[],[1145,1146],[],[1147],[1148],[],[1149,1150],[],[456,1151],[1152,1153,600],[597],[],[1154,1155,418,1156,1157,1158,103],[],[],[],[1159,64,1160,1161,1162],[1163],[],[],[1164],[1165,1166],[1167],[1168,1169,81,1170],[1171,1172],[],[1173],[1174,457,1175,1176],[],[1177,243,1178,1179,295,386],[1180,227],[],[],[147,180],[1181,1182],[],[],[],[60],[1183],[],[363],[],[1184],[],[1185],[],[1186],[317,411],[],[],[],[],[1187,1188,171],[1189,342,228,550],[1190,503,1191,1192,1193],[1194],[1195,1196],[],[1197,1198,1199,1200],[],[454,1201,1202,586,214,329,1203,1204,1205,88,1206,1207,523,555,177,1208],[1209,55],[],[1210,281,1211,103],[],[],[1212,1213,1214,314,1215,1216],[],[],[126,1217],[1218,1219],[1220,1221,1222],[],[197],[],[1223,1224,1225],[],[1226,1227],[1228,1229],[1230],[1231,249],[],[1232,1233,1234,1235],[1236],[1237],[554,198],[1238],[115,1239],[1240,182],[1241,1242],[1243],[],[272,189,1244],[1245],[],[1246,344,1247,429,457,1248,1249,1250,1251],[1252,324,1253,1254],[],[456,123,1255],[1256],[1257],[1258,250],[],[],[],[1259,1260,1261,1262,457],[1263,1264,1265,1266,1267,1268,1269,372,313,1270,1271,1272,1273],[],[1274],[],[1275,403],[1276,179],[],[],[1277],[1278,1279,1280,1281,115,1282,1283],[1284,157,198,1285,1286],[353,1287,1288,1289],[4,1290],[129],[],[1291,1292,1293],[],[120,1294],[1295],[1296],[1297,1298],[1299],[],[],[338,14],[367],[1300,1301],[185,1302],[1303,1304],[1305,115,1306],[],[241],[1307],[1308],[1309],[1310],[1311],[1312],[1313],[437],[438],[524],[1314],[1315],[1316],[157],[1317],[1318],[210],[241],[1319],[1320],[1321],[524],[1322],[1323],[1324],[1325],[1326],[1327],[1328],[1329],[1330],[1331],[524],[1332],[1333],[1334],[1335],[1336],[1337],[1338],[1339],[1340],[386],[1341],[1342],[1343],[386],[1344],[1345],[1346],[447],[1347],[1348],[1349],[1350],[1351],[1352],[1353],[1354],[1355],[1356],[1357],[1358],[1359],[1360],[1361],[210],[1362],[1363],[1364],[1365],[1366],[333],[14],[1367],[1368],[1369],[1370],[1371],[1372],[1373],[1374],[530],[1375],[1376],[1377],[1378],[1379],[1380],[1381],[1382],[1383],[1384],[1385],[1386],[1387],[1388],[1389],[1390],[1391],[1392],[1393],[243],[1394],[295],[1395],[1396],[1397],[1398],[333],[1399],[530],[1400],[1401],[1402],[1403],[1404],[1405],[1406],[1407],[210],[1408],[1409],[1410],[1411],[1412],[1413],[1414],[1415],[1416],[1417],[1418],[1419],[1420],[1421],[1422],[1423],[1424],[241],[1425],[1426],[1427],[1428],[1429],[324],[1430],[1431],[1432],[241],[1433],[1434],[1435],[329],[333],[1436],[1437],[1438],[1439],[333],[1440],[1441],[1442],[1443],[1444],[1445],[1446],[1447],[1448],[1449],[1450],[1451],[1452],[1453],[1454],[14],[1455],[1456],[1457],[1458],[1459],[1460],[1461],[1462],[386],[1463],[1464],[1465],[1466],[1467],[1468],[241],[1469],[1470],[1471],[1472],[1473],[1474],[60],[1475],[1476],[205],[530],[1477],[1478],[1479],[1480],[1481],[1482],[1483],[1484],[1485],[1486],[1487],[1488],[1489],[333],[1490],[1491],[1492],[1493],[1494],[1495],[157],[182],[1496],[1497],[1498],[1499],[1500],[1501],[1502],[173],[1503],[510],[1504],[601],[1505],[1506],[1507],[1508],[1509],[1510],[1511],[1512],[1513],[1514],[1515],[1516],[1517],[1518],[18],[1519],[1520],[1521],[1522],[1523],[317],[1524],[1525],[1526],[1527],[1528],[1529],[1530],[1531],[1532],[1533],[1534],[1535],[1536],[586],[1537],[1538],[1539],[1540],[1541],[1542],[1543],[1544],[1545],[1546],[432],[1547],[1548],[1549],[524],[1550],[1551],[524],[1552],[1553],[90],[1554],[151],[1555],[1556],[1557],[333],[173],[1558],[1559],[182],[333],[1560],[1561],[159],[1562],[530],[1563],[1564],[1565],[1566],[1567],[1568],[1569],[1570],[1571],[205],[1572],[1573],[1574],[1575],[1576],[1577],[173],[1578],[1579],[333],[241],[1580],[1581],[1582],[1583],[1584],[1585],[1586],[1587],[1588],[1589],[1590],[1591],[1592],[1593],[1594],[1595],[1596],[1597],[1598],[1599],[1600],[1601],[524],[1602],[222],[1603],[1604],[182],[22],[1605],[307],[1606],[1607],[1608],[524],[1609],[241],[1610],[1611],[86],[572],[1612],[242],[1613],[324],[1614],[1615],[1616],[601],[1617],[1618],[1619],[14],[1620],[1621],[1622],[312],[1623],[1624],[1625],[483],[1626],[1627],[1628],[324],[1629],[1630],[1631],[333],[1632],[1633],[1634],[1635],[90],[1636],[1637],[14],[1638],[1639],[1640],[1641],[1642],[241],[1643],[1644],[1645],[1646],[1647],[1648],[1649],[1650],[1651],[210],[1652],[333],[1653],[1654],[1655],[348],[421],[1656],[22],[1657],[515],[1658],[329],[14],[517],[1659],[1660],[1661],[1662],[1663],[1664],[1665],[241],[1666],[241],[454],[1667],[1668],[1669],[1670],[1671],[333],[1672],[1673],[1674],[1675],[1676],[1677],[1678],[1679],[1680],[1681],[1682],[1683],[1684],[1685],[159],[1686],[1687],[1688],[1689],[1690],[1691],[1692],[1693],[1694],[324],[1695],[1696],[1697],[1698],[1699],[1700],[1701],[1702],[1703],[1704],[1705],[1706],[324],[1707],[1708],[1709],[222],[1710],[524],[1711],[1712],[1713],[1714],[1715],[378],[14],[1716],[1717],[498],[1718],[1719],[1720],[1721],[1722],[1723],[515],[1724],[1725],[1726],[1727],[524],[1728],[1729],[1730],[14],[1731],[348],[1732],[1733],[1734],[1735],[1736],[1737],[1738],[1739],[164],[1740],[1741],[1742],[1743],[378],[438],[1744],[1745],[1746],[14],[1747],[1748],[1749],[1750],[1751],[447],[1752],[1753],[1754],[1755],[1756],[1757],[1758],[1759],[1760],[1761],[1762],[530],[1763],[1764],[1765],[1766],[447],[14],[1767],[1768],[104],[1769],[1770],[1771],[241],[1772],[1773],[1774],[1775],[1776],[86],[1777],[1778],[1779],[1780],[1781],[338],[1782],[1783],[1784],[1785],[1786],[1787],[1788],[157],[1789],[342],[198],[1790],[1791],[1792],[1793],[1794],[1795],[1796],[1797],[245],[1798],[1799],[1800],[1801],[210],[1802],[1803],[1804],[1805],[1806],[1807],[1808],[524],[1809],[329],[1810],[1811],[1812],[1813],[1814],[1815],[483],[1816],[1817],[90],[1818],[1819],[1820],[158],[1821],[1822],[566],[1823],[1824],[1825],[1826],[1827],[1828],[1829],[1830],[1831],[1832],[241],[1833],[1834],[1835],[1836],[1837],[1838],[1839],[1840],[207],[225],[1841],[1842],[1843],[1844],[1845],[1846],[1847],[1848],[1849],[1850],[1851],[1852],[1853],[1854],[1855],[243],[1856],[1857],[1858],[1859],[1860],[1861],[1862],[1863],[1864],[1865],[1866],[1867],[329],[1868],[1869],[1870],[1871],[515],[1872],[1873],[1874],[1875],[1876],[1877],[1878],[421],[1879],[1880],[1881],[1882],[1883],[1884],[1885],[1886],[1887],[329],[1888],[1889],[1890],[1891],[1892],[1893],[1894],[554],[1895],[1896],[1897],[1898],[1899],[1900],[1901],[1902],[1903],[1904],[1905],[1906],[1907],[1908],[1909],[1910],[363],[1911],[329],[1912],[1913],[586],[1914],[1915],[1916],[1917],[1918],[1919],[1920],[1921],[1922],[329],[1923],[1924],[1925],[1926],[1927],[1928],[1929],[1930],[1931],[1932],[348],[1933],[1934],[1935],[1936],[1937],[329],[329],[1938],[1939],[1940],[1941],[1942],[329],[1943],[1944],[1945],[1946],[1947],[1948],[1949],[1950],[1951],[1952],[291],[104],[1953],[1954],[1955],[1956],[106],[1957],[329],[1958],[1959],[1960],[1961],[1962],[1963],[1964],[1965],[342],[1966],[1967],[1968],[1969],[1970],[1971],[198],[1972],[1973],[1974],[1975],[1976],[90],[329],[1977],[1978],[1979],[1980],[348],[1981],[1982],[1983],[437],[342],[1984],[1985],[1986],[228],[1987],[1988],[1989],[1990],[1991],[1992],[1993],[1994],[1995],[1996],[1997],[1998],[1999],[2000],[2001],[2002],[2003],[2004],[2005],[2006],[104],[2007],[2008],[2009],[329],[2010],[2011],[334],[2012],[2013],[2014],[2015],[2016],[363],[2017],[2018],[2019],[2020],[2021],[2022],[2023],[2024],[2025],[2026],[2027],[2028],[2029],[2030],[2031],[2032],[329],[2033],[517],[2034],[2035],[2036],[90],[2037],[2038],[2039],[2040],[150],[2041],[2042],[242],[2043],[329],[2044],[367],[2045],[2046],[2047],[489],[324],[2048],[2049],[2050],[2051],[243],[2052],[2053],[2054],[2055],[2056],[2057],[90],[2058],[2059],[2060],[243],[2061],[367],[2062],[2063],[498],[2064],[342],[2065],[2066],[2067],[2068],[2069],[2070],[2071],[2072],[2073],[2074],[2075],[2076],[2077],[2078],[2079],[2080],[2081],[2082],[2083],[2084],[2085],[329],[2086],[329],[2087],[2088],[2089],[2090],[2091],[2092],[2093],[2094],[2095],[2096],[454],[2097],[151],[2098],[2099],[2100],[2101],[2102],[2103],[2104],[562],[2105],[2106],[2107],[329],[2108],[2109],[2110],[2111],[2112],[2113],[2114],[2115],[2116],[329],[2117],[2118],[2119],[2120],[348],[503],[2121],[2122],[2123],[2124],[2125],[2126],[2127],[2128],[2129],[2130],[2131],[2132],[2133],[2134],[2135],[2136],[2137],[2138],[2139],[2140],[2141],[2142],[2143],[2144],[2145],[329],[2146],[329],[2147],[2148],[2149],[2150],[2151],[2152],[2153],[2154],[2155],[2156],[2157],[2158],[106],[329],[2159],[2160],[2161],[2162],[2163],[2164],[2165],[329],[2166],[324],[329],[18],[2167],[2168],[2169],[2170],[562],[601],[410],[2171],[2172],[2173],[2174],[2175],[2176],[2177],[2178],[589],[2179],[2180],[2181],[2182],[2183],[2184],[329],[2185],[2186],[2187],[2188],[2189],[2190],[2191],[143],[2192],[2193],[2194],[2195],[2196],[2197],[2198],[2199],[2200],[2201],[2202],[329],[2203],[2204],[2205],[2206],[329],[2207],[2208],[2209],[2210],[2211],[2212],[2213],[2214],[2215],[86],[2216],[2217],[2218],[243],[2219],[2220],[2221],[2222],[2223],[2224],[2225],[2226],[2227],[348],[2228],[2229],[2230],[2231],[2232],[2233],[2234],[2235],[2236],[329],[2237],[324],[2238],[2239],[2240],[2241],[2242],[363],[329],[329],[2243],[2244],[2245],[2246],[2247],[2248],[2249],[2250],[2251],[2252],[2253],[2254],[2255],[2256],[329],[2257],[2258],[2259],[2260],[2261],[2262],[2263],[2264],[2265],[2266],[2267],[2268],[2269],[2270],[2271],[295],[386],[2272],[90],[106],[2273],[2274],[2275],[243],[2276],[367],[2277],[86],[2278],[348],[2279],[2280],[307],[586],[2281],[329],[2282],[2283],[2284],[2285],[2286],[324],[2287],[2288],[2289],[2290],[2291],[324],[2292],[2293],[2294],[2295],[2296],[2297],[2298],[2299],[2300],[2301],[2302],[2303],[324],[2304],[2305],[2306],[295],[386],[363],[329],[2307],[2308],[2309],[2310],[2311],[2312],[90],[421],[106],[22],[382],[2313],[2314],[2315],[2316],[348],[2317],[2318],[2319],[329],[2320],[2321],[2322],[177],[246],[2323],[2324],[2325],[2326],[324],[307],[2327],[2328],[348],[2329],[2330],[2331],[2332],[2333],[324],[2334],[2335],[2336],[2337],[2338],[2339],[2340],[157],[2341],[295],[2342],[2343],[2344],[2345],[2346],[437],[2347],[2348],[295],[2349],[386],[2350],[2351],[86],[2352],[2353],[2354],[489],[2355],[2356],[2357],[342],[2358],[342],[2359],[158],[2360],[2361],[550],[342],[2362],[2363],[2364],[2365],[2366],[2367],[2368],[2369],[157],[2370],[437],[2371],[2372],[295],[2373],[2374],[2375],[2376],[2377],[2378],[2379],[2380],[342],[2381],[2382],[2383],[2384],[2385],[86],[2386],[437],[2387],[2388],[342],[2389],[2390],[410],[2391],[2392],[2393],[2394],[2395],[601],[437],[342],[437],[2396],[2397],[342],[2398],[228],[2399],[2400],[2401],[86],[572],[2402],[572],[2403],[86],[2404],[2405],[2406],[2407],[295],[489],[295],[2408],[2409],[2410],[198],[2411],[2412],[2413],[2414],[2415],[517],[437],[2416],[157],[498],[2417],[2418],[2419],[2420],[2421],[2422],[2423],[198],[2424],[2425],[572],[2426],[2427],[2428],[2429],[2430],[342],[2431],[242],[2432],[2433],[2434],[342],[2435],[2436],[601],[2437],[342],[2438],[342],[18],[157],[2439],[2440],[291],[2441],[2442],[2443],[601],[2444],[2445],[411],[2446],[2447],[2448],[2449],[2450],[2451],[2452],[2453],[2454],[342],[2455],[2456],[2457],[2458],[2459],[2460],[2461],[46],[2462],[2463],[2464],[2465],[2466],[2467],[2468],[2469],[2470],[2471],[2472],[2473],[377],[86],[2474],[158],[342],[2475],[2476],[2477],[243],[2478],[342],[2479],[2480],[342],[2481],[2482],[243],[2483],[2484],[601],[242],[2485],[342],[228],[2486],[2487],[2488],[2489],[2490],[198],[157],[601],[410],[498],[2491],[2492],[2493],[2494],[2495],[2496],[2497],[2498],[2499],[342],[2500],[2501],[2502],[2503],[2504],[2505],[198],[342],[2506],[489],[2507],[2508],[2509],[334],[2510],[2511],[158],[342],[2512],[2513],[342],[2514],[2515],[295],[2516],[2517],[2518],[246],[2519],[2520],[2521],[2522],[2523],[2524],[2525],[2526],[2527],[2528],[410],[2529],[2530],[295],[2531],[2532],[2533],[2534],[2535],[2536],[342],[228],[2537],[2538],[2539],[2540],[342],[2541],[2542],[2543],[2544],[489],[157],[272],[2545],[228],[2546],[2547],[367],[2548],[2549],[2550],[342],[228],[2551],[2552],[2553],[437],[2554],[2555],[562],[2556],[342],[2557],[2558],[2559],[2560],[2561],[342],[2562],[342],[2563],[2564],[2565],[2566],[2567],[2568],[2569],[2570],[437],[2571],[2572],[295],[2573],[386],[2574],[2575],[2576],[483],[342],[228],[2577],[2578],[104],[2579],[2580],[2581],[2582],[342],[550],[228],[157],[2583],[2584],[572],[2585],[2586],[386],[2587],[2588],[2589],[2590],[198],[2591],[2592],[342],[437],[2593],[342],[2594],[2595],[259],[554],[2596],[2597],[2598],[2599],[157],[342],[2600],[2601],[2602],[2603],[2604],[562],[334],[2605],[2606],[158],[2607],[2608],[2609],[242],[2610],[2611],[2612],[2613],[2614],[2615],[2616],[246],[2617],[157],[2618],[334],[2619],[2620],[2621],[2622],[2623],[2624],[2625],[2626],[2627],[2628],[2629],[2630],[2631],[2632],[2633],[342],[129],[2634],[2635],[2636],[2637],[2638],[2639],[2640],[2641],[2642],[2643],[489],[342],[157],[18],[2644],[2645],[2646],[2647],[342],[2648],[2649],[342],[2650],[2651],[2652],[2653],[2654],[2655],[2656],[334],[157],[2657],[572],[2658],[2659],[2660],[2661],[198],[498],[2662],[2663],[2664],[2665],[2666],[483],[2667],[2668],[367],[367],[2669],[2670],[2671],[483],[2672],[2673],[2674],[2675],[295],[242],[2676],[562],[562],[2677],[2678],[2679],[243],[2680],[2681],[386],[2682],[2683],[367],[367],[2684],[2685],[2686],[2687],[572],[2688],[2689],[2690],[2691],[2692],[86],[367],[2693],[2694],[2695],[2696],[295],[158],[2697],[2698],[2699],[2700],[562],[2701],[367],[2702],[86],[2703],[2704],[2705],[2706],[483],[2707],[2708],[2709],[2710],[2711],[2712],[86],[2713],[483],[2714],[2715],[317],[2716],[2717],[2718],[386],[295],[2719],[2720],[2721],[2722],[2723],[2724],[86],[2725],[562],[2726],[2727],[2728],[2729],[2730],[86],[2731],[2732],[86],[2733],[483],[2734],[2735],[367],[2736],[2737],[2738],[2739],[295],[291],[2740],[2741],[242],[2742],[2743],[2744],[2745],[242],[2746],[2747],[2748],[2749],[2750],[242],[2751],[2752],[2753],[2754],[2755],[2756],[2757],[158],[158],[317],[2758],[377],[86],[2759],[2760],[377],[2761],[2762],[2763],[104],[2764],[2765],[86],[2766],[243],[2767],[2768],[243],[2769],[2770],[243],[2771],[295],[158],[2772],[86],[86],[246],[2773],[512],[165],[86],[242],[2774],[2775],[367],[2776],[2777],[2778],[562],[2779],[2780],[2781],[2782],[2783],[2784],[2785],[2786],[386],[2787],[295],[386],[2788],[2789],[2790],[2791],[2792],[2793],[2794],[2795],[86],[367],[2796],[2797],[572],[2798],[2799],[86],[367],[2800],[2801],[86],[2802],[2803],[2804],[295],[386],[86],[2805],[2806],[242],[2807],[2808],[377],[2809],[2810],[2811],[86],[572],[249],[483],[2812],[317],[86],[2813],[2814],[2815],[2816],[2817],[2818],[2819],[2820],[2821],[2822],[2823],[2824],[483],[2825],[2826],[2827],[2828],[2829],[2830],[2831],[517],[86],[242],[2832],[86],[86],[572],[2833],[2834],[2835],[2836],[242],[242],[367],[2837],[2838],[2839],[562],[2840],[2841],[2842],[2843],[2844],[2845],[2846],[2847],[367],[2848],[2849],[2850],[2851],[2852],[2853],[86],[572],[2854],[2855],[2856],[2857],[2858],[2859],[2860],[295],[2861],[2862],[2863],[2864],[2865],[2866],[2867],[2868],[295],[386],[2869],[2870],[2871],[2872],[243],[2873],[2874],[2875],[2876],[242],[377],[2877],[2878],[295],[386],[2879],[2880],[2881],[2882],[572],[2883],[2884],[246],[2885],[2886],[2887],[2888],[2889],[2890],[2891],[483],[2892],[2893],[2894],[2895],[317],[2896],[165],[246],[2897],[2898],[2899],[2900],[2901],[2902],[2903],[246],[2904],[483],[246],[2905],[2906],[2907],[2908],[2909],[2910],[2911],[246],[2912],[2913],[246],[246],[2914],[2915],[2916],[2917],[2918],[2919],[2920],[2921],[2922],[2923],[2924],[2925],[2926],[2927],[104],[2928],[2929],[2930],[2931],[2932],[2933],[2934],[2935],[2936],[2937],[158],[2938],[2939],[2940],[2941],[2942],[2943],[246],[2944],[2945],[2946],[2947],[2948],[2949],[2950],[2951],[2952],[2953],[2954],[2955],[2956],[2957],[2958],[2959],[158],[158],[46],[2960],[2961],[2962],[2963],[246],[2964],[2965],[2966],[2967],[246],[2968],[246],[483],[2969],[104],[317],[2970],[2971],[2972],[165],[2973],[2974],[2975],[317],[2976],[2977],[2978],[2979],[2980],[2981],[2982],[2983],[2984],[158],[246],[246],[2985],[2986],[2987],[2988],[2989],[317],[2990],[483],[2991],[246],[2992],[246],[2993],[2994],[2995],[2996],[2997],[158],[483],[2998],[2999],[3000],[3001],[165],[246],[3002],[3003],[3004],[3005],[158],[3006],[246],[3007],[3008],[3009],[3010],[3011],[3012],[3013],[3014],[3015],[3016],[317],[3017],[158],[3018],[3019],[3020],[158],[3021],[3022],[3023],[3024],[562],[3025],[3026],[246],[3027],[3028],[3029],[246],[246],[3030],[3031],[3032],[3033],[483],[3034],[158],[3035],[3036],[3037],[3038],[3039],[3040],[3041],[3042],[3043],[562],[246],[3044],[3045],[46],[3046],[3047],[3048],[3049],[3050],[246],[3051],[3052],[3053],[3054],[3055],[3056],[562],[3057],[3058],[3059],[562],[3060],[3061],[3062],[3063],[3064],[158],[3065],[3066],[3067],[3068],[562],[562],[3069],[3070],[3071],[3072],[3073],[562],[3074],[3075],[158],[3076],[158],[3077],[3078],[3079],[3080],[158],[3081],[3082],[562],[562],[3083],[3084],[3085],[3086],[3087],[3088],[562],[3089],[3090],[3091],[3092],[3093],[158],[3094],[3095],[3096],[3097],[3098],[3099],[158],[3100],[3101],[3102],[3103],[3104],[3105],[3106],[3107],[3108],[3109],[3110],[3111],[3112],[3113],[3114],[3115],[562],[3116],[3117],[3118],[3119],[3120],[3121],[3122],[3123],[3124],[3125],[3126],[3127],[3128],[3129],[3130],[3131],[158],[562],[3132],[3133],[272],[3134],[3135],[3136],[3137],[158],[562],[3138],[3139],[3140],[3141],[158],[3142],[3143],[3144],[3145],[3146],[3147],[3148],[3149],[3150],[3151],[3152],[562],[3153],[158],[3154],[3155],[3156],[3157],[158],[3158],[3159],[562],[3160],[3161],[3162],[3163],[3164],[3165],[3166],[158],[434],[3167],[3168],[3169],[3170],[3171],[3172],[3173],[3174],[3175],[3176],[3177],[3178],[3179],[3180],[3181],[3182],[3183],[3184],[3185],[3186],[3187],[3188],[3189],[3190],[3191],[3192],[158],[3193],[3194],[3195],[3196],[3197],[3198],[3199],[3200],[562],[158],[3201],[3202],[3203],[3204],[562],[3205],[3206],[3207],[562],[3208],[3209],[3210],[3211],[3212],[3213],[562],[3214],[3215],[3216],[3217],[3218],[562],[3219],[3220],[3221],[3222],[3223],[3224],[562],[3225],[562],[3226],[3227],[3228],[3229],[3230],[158],[562],[3231],[158],[158],[3232],[3233],[158],[562],[3234],[3235],[3236],[3237],[3238],[3239],[3240],[3241],[3242],[158],[158],[3243],[3244],[158],[158],[3245],[3246],[562],[3247],[562],[3248],[562],[3249],[3250],[3251],[3252],[562],[3253],[3254],[158],[562],[3255],[562],[562],[562],[3256],[3257],[3258],[3259],[562],[562],[3260],[562],[3261],[3262],[3263],[3264],[3265],[3266],[158],[158],[562],[3267],[3268],[189],[3269],[562],[3270],[3271],[562],[3272],[3273],[3274],[3275],[158],[562],[3276],[158],[3277],[3278],[562],[3279],[3280],[3281],[562],[3282],[3283],[3284],[3285],[3286],[3287],[3288],[562],[3289],[3290],[3291],[3292],[3293],[562],[562],[3294],[562],[3295],[3296],[3297],[158],[158],[158],[3298],[3299],[3300],[158],[3301],[158],[3302],[3303],[3304],[3305],[3306],[3307],[3308],[158],[3309],[158],[158],[158],[158],[158],[158],[3310],[158],[189],[3311],[158],[3312],[158],[3313],[3314],[3315],[158],[3316],[3317],[3318],[3319],[3320],[3321],[3322],[3323],[3324],[158],[158],[3325],[158],[3326],[189],[158],[272],[158],[272],[3327],[3328],[3329],[3330],[158],[158],[3331],[3332],[272],[158],[3333],[3334],[158],[3335],[3336],[158],[3337],[3338],[3339],[3340],[158],[158],[3341],[3342],[3343],[3344],[3345],[3346],[3347],[158],[272],[3348],[3349],[3350],[3351],[3352],[3353],[158],[158],[3354],[158],[3355],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158],[158]]
num_layers = 10
# Determine how much memory to allocate
var_count = count_mem(layer_verts, adj_list, num_layers)
println("FOR LOOP ITER TIME")
@time var_count = count_mem(layer_verts, adj_list, num_layers)
# ----
println("IMMUTABLE")
gc()
bench_immutable(layer_verts, adj_list, num_layers, var_count)
gc()
bench_immutable(layer_verts, adj_list, num_layers, var_count)
gc()
bench_immutable(layer_verts, adj_list, num_layers, var_count)
# ----
println("NTUPLE{INT,5}")
gc()
bench_fulltuple(layer_verts, adj_list, num_layers, var_count)
gc()
bench_fulltuple(layer_verts, adj_list, num_layers, var_count)
gc()
bench_fulltuple(layer_verts, adj_list, num_layers, var_count)
# ----
println("NTUPLE{5}")
gc()
bench_partialtuple(layer_verts, adj_list, num_layers, var_count)
gc()
bench_partialtuple(layer_verts, adj_list, num_layers, var_count)
gc()
bench_partialtuple(layer_verts, adj_list, num_layers, var_count)Julia 0.3.7Julia 0.4.0-dev+4893 (2015-05-19 11:51 UTC) |
|
@JeffBezanson would be curious to see the output of that perf testing script if you have it handy (or I can just wait for next nightly) |
|
Now this is one heck of a performance fix. -100 lines of code! +:100: |
|
Here's what I got from running the script: |
|
Wow, game changing! |
|
Yes, #10380 isn't all bad :) |
|
Yay! Re #10380, for better or for worse the importance of changes often seems measured by how much stuff they break :-). |
|
Speaking of breaking, the fix seems to have broken the non-inlined coverage test buildbot: http://buildbot.e.ip.saba.us:8010/builders/coverage_ubuntu14.04-x64 |
|
I was going to say, we perhaps need to just shift some tests to running only with inlining. But a segfault was a different form of breakage than I anticipated: I can replicate on current master (HEAD at 42243c4) with So it's segfaulting during codegen. Here's a minimal test: julia> using Base.Test
julia> A = sprandbool(5,5,0.2);
julia> @test_throws DimensionMismatch reinterpret(Int8,A,(20,))
signal (11): Segmentation fault
unknown function (ip: -245467824)
Segmentation fault (core dumped) |
|
I get an assertion failure: |
see comment in #11100 ideally, any Tuple containing Union() should collapse to Union(), but I will just put a bandaid on this for now.
|
Ok, that specific problem should be fixed now. |
|
Nice! |
see comment in JuliaLang#11100 ideally, any Tuple containing Union() should collapse to Union(), but I will just put a bandaid on this for now.
see comment in JuliaLang#11100 ideally, any Tuple containing Union() should collapse to Union(), but I will just put a bandaid on this for now.
Edit: revised benchmarking script and results on latest master here
Problem: building a dictionary with 5-int-tuple keys and int values is really quite slow. Sizehint-ing makes it about twice as fast, but theres an amazing amount of garbage generated even when there is no particular need (as far as I can tell).
Test code (with real data):
Julia 0.3.7
Version 0.4.0-dev+4590 (2015-05-01 22:48 UTC)
The text was updated successfully, but these errors were encountered: