Ing. Martin Bak, vedoucí týmu vývoje martin.bak@firma.seznam.cz Vektorové mapy www.seznam.cz Vektorové mapy Martin Bak Mobilní tým ● backend ● technologie, nástroje Cesta vektorů do aplikace ● úpravy, optimalizace ● kódování / komprese Jak to celé funguje v provozu 2/48 www.seznam.cz Mobilní tým Martin Bak 3/48 Aplikační platformy iOS ● 3 vývojáři Android ● 3 vývojáři Windows Phone ● 2 vývojáři Backend 3 vývojáři Objective-C, C++ Java, C++ C++ C++, Python, JavaScript, .. Subversion, GIT MySQL, PostgreSQL Debian (squeeze, wheezy) www.seznam.cz Mobilní tým - aplikace Martin Bak 4/48 www.seznam.cz Mobilní tým - backend Martin Bak 5/48 Samostatné systémy SMS Brána Podpůrné služby ImageSizer Detekce Statistiky + Adminweby Backendy pro aplikace Novinky.cz Mapy.cz Platformy WSGI Publisher SiteBuilder Mnoho dalších knihoven.. www.seznam.cz Aplikace Mapy.cz Martin Bak 6/48 Předchozí verze Vše v rastru Mnoho verzí aplikací / backendů www.seznam.cz Vektorová data Martin Bak 7/48 Příprava dat Kreslená ručně → je potřeba mnoho (strojových) oprav ● Spojování geometrií ● Odečítání polygonů ● Odstraňování děr a špiček ● Zjednodušování geometrií ● Příprava textových „výpalů“ ● … ● Konvexizace a dekompozice polygonů ● Komprese a kódování dat (barelování) www.seznam.cz Spojování geometrií Martin Bak 8/48 www.seznam.cz Spojování geometrií Martin Bak 9/48 www.seznam.cz Spojování geometrií Martin Bak 10/48 www.seznam.cz Spojování geometrií Martin Bak 11/48 www.seznam.cz Spojování geometrií Martin Bak 12/48 www.seznam.cz Odečítání polygonů Martin Bak 13/48 www.seznam.cz Odečítání polygonů Martin Bak 14/48 www.seznam.cz Odečítání polygonů Martin Bak 15/48 www.seznam.cz Odstraňování děr a špiček Martin Bak 16/48 www.seznam.cz Odstraňování děr a špiček Martin Bak 17/48 www.seznam.cz Odstraňování děr a špiček Martin Bak 18/48 www.seznam.cz Zjednodušování geometrií Martin Bak 19/48 0 m, 728 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 20/48 2 m, 377 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 21/48 4 m, 262 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 22/48 8 m, 178 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 23/48 16 m, 114 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 24/48 32 m, 69 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 25/48 64 m, 42 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 26/48 128 m, 31 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 27/48 256 m, 23 bodů www.seznam.cz Zjednodušování geometrií Martin Bak 28/48 512 m, 18 bodů www.seznam.cz Příprava textových „výpalů“ Martin Bak 29/48 www.seznam.cz Příprava textových „výpalů“ Martin Bak 30/48 www.seznam.cz Konvexizace polygonů Martin Bak 31/48 www.seznam.cz Konvexizace polygonů Martin Bak 32/48 konvexní nekonvexní www.seznam.cz Konvexizace polygonů Martin Bak 33/48 www.seznam.cz Polygon viditelnosti Martin Bak 34/48 www.seznam.cz Polygon viditelnosti Martin Bak 35/48 www.seznam.cz Polygon viditelnosti Martin Bak 36/48 www.seznam.cz Matice viditelnosti Martin Bak 37/48   0 1 2 3 4 5 0 1 1 1 0 0 1 1 1 1 1 1 0 1 2 1 1 1 1 1 1 3 0 1 1 1 1 1 4 0 0 1 1 1 1 5 1 1 1 1 1 1 0 5 4 3 2 1 www.seznam.cz Konvexizace – CUDA odbočka Martin Bak 38/48 www.seznam.cz CUDA – organizace vláken Martin Bak 39/48 www.seznam.cz CUDA – organizace pamětí Martin Bak 40/48 www.seznam.cz CUDA – konvexizace polygonů Martin Bak 41/48 Data 200000 náhodně vybraných polygonů s počtem bodů do 400 HW CPU ● Intel Xeon E5645 @ 2,4 GHz GPU  nVidia Tesla M2075 - 448 CUDA jader @ 1,15 GHz www.seznam.cz CUDA – konvexizace polygonů Martin Bak 42/48 www.seznam.cz CUDA – konvexizace polygonů Martin Bak 43/48 Na nejmenších polygonech (4 body) ● zrychlení cca 30% Od cca 10 bodů ● zrychlení řádové (10x) Na největší polygonech (~400 bodů) ● zrychlení až o 3 řády (~ 1000x) www.seznam.cz Komprese dat (barelování) Martin Bak 44/48 Barel Binární reprezentace oblasti Skládá se ze subbarelů hloubka 1 hloubka 4hloubka 3hloubka 2 www.seznam.cz Komprese dat (barelování) Martin Bak 45/48 0000000 0c1e 2153 9200 002a 224f 3300 001c 1403 0000010 c700 0017 1bbc 1f00 0015 26d3 5200 0033 0000020 2fcf eb00 001d 1c64 4900 001e 2761 a000 0000030 0019 2779 cd00 001d 31ce 3000 0026 1d55 0000040 3100 0021 11da 4500 0011 2727 5c00 0015 0000050 198d 5300 001c 1b68 e500 0016 1381 6800 0000060 0012 1752 3900 0012 1b5b 2800 001c 1d1d 0000070 6800 0013 11f1 8d00 000a 1e99 5f00 001f 0000080 157f 8400 0018 144e d700 000f 1378 7e00 0000090 0016 14ea b900 000f 098c 5a00 0011 1b5c 00000a0 2e00 001a 1380 cb00 0018 14e5 ad00 0012 00000b0 0b5c 8500 000a 0b8c 2a00 001a 145b b200 00000c0 0010 2184 b6ca 9835 edf1 074e ac1f 179b 00000d0 1c5d 8d83 805c 9941 0870 8557 87be f052 00000e0 6060 6060 6060 6060 6060 6060 a0a0 a0a0 00000f0 a0a0 a0a0 a0a0 a0a0 a0a0 0110 0101 abab 0000100 abab 0101 0001 7f00 0000 01de f300 0000 0000110 001b 1800 0000 06ba 3300 0000 002a 1d00 Barel Více zoomů v jednom barelu Komprese a kódování dat ● Blokové ● Fibonacciho XML Styly – jak se který vektor vykreslí www.seznam.cz A jak je to v provozu? Martin Bak 46/48 Backend 8 strojů (2 x 4) ● 4 x backend, 8 x výdej dat Při nasazení: ● 8 x 1 Gb ● 8 x 2 Gb ● 2 x 10 Gb Při nasazení cca 9MB/s z každého stroje, teď cca 1 MB/s FastRPC protokol www.seznam.cz A jak je to v provozu? Martin Bak 47/48 Aplikace Android ● 50 000 uživatelů iOS ● 30 000 uživatelů WP8 ● bude se vidět .-) www.seznam.cz Martin Bak Díky za pozornost