Immortal C ++, Python uygulamalarını 8000 kat hızlandırır!
Yapay zeka dalgası altında, tüm insanların Python'u öğrenmesi kaçınılmaz bir trend haline geldi. Bir yapıştırıcı dil olarak Python, basit sözdizimi, iyi etkileşimi, taşınabilirliği ve diğer avantajları nedeniyle birçok geliştirici tarafından sevilir.Peki eski C ++ ile karşılaştırıldığında kim daha hızlı çalışır? Pek çok geliştiricinin şüphesiz C ++ 'yı seçeceğine inanıyorum ve bu makalenin yazarı bunu onayladı.
Aşağıdaki çeviridir:
Son zamanlarda, yerel bir müzik kitaplığını yönetmek için bir müzik yöneticisi olan Bard (https://github.com/antlarr/bard) adında bir komut satırı uygulaması geliştiriyorum. Bard, şarkılara göre (acoustid kullanarak: https://acoustid.org/) ses parmak izleri oluşturacak ve tüm şarkıların meta verilerini sqlite veritabanına kaydedecektir. Bu şekilde, şarkıların etiketleri yanlış olsa bile yinelenen şarkıları kolayca arayabilir ve bulabilirsiniz. Bu makalenin yazarı, yinelenen şarkıları bulmak için algoritmayı paylaşıyor ve algoritmayı iki kez optimize etmek için Python ve C ++ 17'yi kullanıyor ve bu algoritmanın orijinalinden 8000 kat daha hızlı nasıl yapılacağını araştırıyor.
algoritma
İki şarkının benzer olup olmadığına karar vermek için ses parmak izlerini karşılaştırmanız gerekir. Kulağa kolay geliyor (aslında zor değil), ancak ilk bakışta göründüğü kadar basit değil. Acoustid tarafından hesaplanan ses parmak izi bir sayı değil, bir sayı dizisidir, daha doğrusu bir karakter dizisidir. Bu nedenle, sayıları karşılaştıramazsınız, sayılardaki karakterleri karşılaştırabilirsiniz. Tüm karakterler tamamen aynıysa, iki şarkı da aynı kabul edilebilir. Karakterlerin% 99'u aynıysa, ikisinin aynı olma ihtimalinin% 99 olduğu düşünülebilir.İkisi arasındaki fark, kodlama sorunlarından kaynaklanıyor olabilir (örneğin, bir şarkı 192kbit / s'de mp3'e kodlanmış ve diğeri 128kbit / s'dir. ) Ve bunun gibi.
Ancak şarkıları karşılaştırırken göz önünde bulundurulması gereken daha çok şey var. Bazen iki şarkının başlangıcındaki boş zamanın uzunluğu farklıdır, bu nedenle parmak izlerinin bitleri tam olarak hizalanmaz ve doğrudan karşılaştırma eşleşmez, ancak parmak izlerinden birini bir konum hareket ettirmek eşleşebilir.
Bu nedenle, iki şarkıyı karşılaştırmak için, yalnızca parmak izlerini karşılaştırmakla kalmamalı, aynı zamanda eşleşme derecelerinin artıp azalmadığını görmek için ilk boş şarkının uzunluğunu artırıp azaltmalıyız. Şu anda Bard diziyi bir yönde 100 bit ve sonra ters yönde 100 bit hareket ettirecek, bu da her şarkının 200 parmak izi karşılaştırması yapması gerektiği anlamına geliyor.
Bu nedenle, bir müzik kitaplığındaki tüm şarkıları kopyaları bulmak için karşılaştırmak istiyorsak, ID1 ve 2'yi karşılaştırmalıyız ve ardından ID 3'ü ID 1 ve ID 2 ile karşılaştırmalıyız. Genel olarak konuşursak, her şarkı önceki tüm şarkılarla karşılaştırılmalıdır. . Bu şekilde müzik kitaplığında 100 şarkı varsa 1000 * 1001/2 = 500500 şarkının karşılaştırılması gerekir (yani 100100000 parmak izini karşılaştırmak için).
İlk Python uygulaması
Bard Python'da yazılmıştır, bu nedenle uygulamanın ilk sürümü, parmak izlerini tamsayı dizilerinde saklamak için Python listelerini kullanır. Yineleme sürecinde her değişiklik yapmam gerektiğinde, parmak izi dizilerinden birinin önüne bir 0 ekleyeceğim ve ardından sırayla her bir öğeyi karşılaştırarak tüm diziyi yineleyeceğim. Karşılaştırma yöntemi, iki öğe üzerinde bir XOR işlemi gerçekleştirmek ve ardından bir tamsayıdaki bit sayısını saymak için bir algoritma kullanmaktır:
def count_bits_set (i):
i = i - ((i > > 1) ve 0x55555555)
i = (i ve 0x33333333) + ((i > > 2) ve 0x33333333)
dönüş (((i + (i > > 4) ve 0xF0F0F0F) * 0x1010101) ve 0xffffffff) > > yirmi dört
Gerçekleşen bu hızı referans değer olarak alıyoruz ve buna çift hız diyoruz.
İlk gelişme
İlk iyileştirme, bit sayma algoritmasını daha hızlı bir gmpy.popcount ( olarak değiştirmeyi denedim ve ayrıca iyileştirmek için bir sonlandırma eşiği ekledim algoritması. Bu yeni algoritma, sonlandırma eşiği aşıldığında bir eşleşmenin imkansız olduğunu belirleyecek ve karşılaştırmayı durduracaktır. Örneğin, hesaplama sürecinde kalan bitlerin tümü eşleşse bile, iki şarkının eşleşme derecesinin% 55'i geçme olasılığı düşüktür, ardından doğrudan "farklı şarkılara" geri dönülür (ancak yine de her ihtimale karşı diğer şarkılarla karşılaştırın) Bir).
Bu iyileştirme, karşılaştırma hızını neredeyse iki katına çıkarır.
C ++ 17 kullanın
Bu noktada, bu kodun daha büyük bir kütüphaneye kolayca genişletilebileceğini düşünmüyorum, bu yüzden Bard'ın daha iyi bir uygulamaya ihtiyacı olduğunu düşünüyorum. Belleği değiştirmek çok yavaştır ve C / C ++ daha ince ayarlı düşük düzeyli optimizasyon sağlayabilir, ancak tüm uygulamayı C ++ ile yeniden yazmak istemiyorum, bu yüzden Boost.Python (https://www.boost.org/doc/libs /1_65_0/libs/python/doc/html/index.html), bu algoritmayı yalnızca C ++ 'da uygulayın ve bu algoritmayı Python uygulamalarından çağırın. Python'a C ++ yöntemlerini entegre etmeyi çok kolay bulduğumu söylemeliyim, bu yüzden Boost.Python'u şiddetle tavsiye ediyorum.
Yeni C ++ uygulamasında, parmak izini kaydetmek için STL vektörünü kullandım ve önceden maksimum ofseti ekledim, böylece algoritmadaki vektördeki öğeleri değiştirmeye gerek kalmaz, sadece yer değiştirmeyi simüle ettim. Ayrıca şarkı kimliğiyle birlikte tüm parmak izlerini dizin olarak saklamak için STL haritasını kullanıyorum. Son olarak, karakterleri hesaplamak için CPU talimatlarını kullanarak gcc'nin __builtin_popcount (https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpopcount) aracılığıyla önemli bir optimizasyon ölçüsü ekledim.
Bu algoritmanın en büyük avantajı, karşılaştırma işleminin herhangi bir parmak izini değiştirmemesi veya kopyalamaması, bu da hızı 126,47 kat artırır. Bu noktada başka bir ölçüt hesaplamaya başladım: saniyede karşılaştırılan şarkı sayısı (karşılaştırılan her şarkı çifti için 200 parmak izi karşılaştırmasının yapıldığını unutmayın). Bu algoritmanın ortalama hızı 580 hareket / saniyedir. Ya da başka bir deyişle, 1000 şarkıyı karşılaştırmak yaklaşık 14 dakika 22 saniye sürer (orijinal Python uygulamasının günde yaklaşık 6 saat, 16 dakika ve 57 saniye sürdüğünü unutmayın).
İlk paralel algoritma denemesi
Brad i bir i7 CPU ile çalıştırıyorum ve her zaman programımın sadece bir CPU kullandığına pişmanım. İki şarkıyı karşılaştırmak için kullanılan algoritma herhangi bir veriyi değiştirmediğinden, 8 çekirdeğin hepsinde birlikte çalışmasını sağlamak ve her yinelemenin sonunda sonuçları birleştirmek için paralel bir algoritma kullanmayı deneyebileceğimi düşünüyorum. Bu yüzden bunu nasıl başaracağımı araştırmaya başladım ve her bir şarkının önceki tüm şarkılarla karşılaştırılmasının, işlenen tüm şarkıları içeren std :: haritası boyunca döngü yaparak elde edildiğini buldum. Bu nedenle, her yinelemeyi farklı bir iş parçacığında çalıştırabilecek her döngü için bir döngü olsaydı harika olurdu. Çıktı! C ++ 17'deki (https://en.cppreference.com/w/cpp/algorithm/for_each) std :: for_each, döngünün farklı evrelerde yürütülebileceği ExecutionPolicy'yi belirleyebilir. Sonra kötü haber var: bu standart henüz gcc tarafından tam olarak desteklenmiyor.
Bu yüzden for_each'in bazı uygulamalarını aradım ve sonunda bir stackoverflow sorusu altında (https://stackoverflow.com/questions/40805197/parallel-for-each-more-than-two-times-slower-than-stdfor-each ) Bir tane buldum. Bu soru "C ++ Eşzamanlı Çalışma" kitabından bir uygulama şemasından bahsediyor. Bu kodun telif hakkından emin değilim, bu yüzden onu doğrudan Brad'e kopyalayamam, ancak ölçüm için bazı testler yapmak için kullanabilirim .
Bu yöntem, hızı 1897 kata veya saniyede yaklaşık 8700 şarkıya çıkarabilir. (1000 şarkının işlenmesi yaklaşık 57 saniye sürer. Çok iyi, doğru!)
İkinci paralel girişim
For_each'in kullanabileceğim paralel bir sürümünü bulmam gerekiyor. Neyse ki sonunda gcc'nin __gnu_parallel :: for_each (https://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode_using.html dahil olmak üzere C ++ standart kitaplığındaki bazı algoritmaların deneysel paralel uygulamalarını içerdiğini buldum. , Dokümantasyon sayfasında daha fazla paralel algoritma vardır). Openmp kitaplığını bağlamanız yeterlidir.
Bu yüzden kodu değiştirdim ve bir sorunla karşılaştım: __gnu_parallel :: for_each'i çağırmama rağmen, her test ettiğimde yalnızca seri olarak çalışacağını buldum! Nedeni bulmak biraz zaman aldı, ancak gcc'nin __gnu_parallel :: for_each uygulamasını okuduktan sonra, rastgele bir erişim yineleyicisi gerektirdiğini fark ettim ( , Ama std :: map üzerinde yinelemesine izin verdim ve harita yapısı rastgele bir yineleyici değil, çift yönlü bir yineleyici.
Ben de std :: map'den parmak izini değiştirmek için kodu değiştirdim < int, std :: vektör < int > > Std'ye kopyala:; vektör < std :: çift < int, std: vektör < int > > > Böylece __gnu_parallel :: for_each, 8 evreli bir evre havuzuyla çalışabilir.
Gcc uygulaması, stackoverflow uygulamasından daha hızlıdır, hız 2442 kat, saniyede yaklaşık 11.200 şarkı ve 1.000 şarkı için yalnızca 44 saniyedir.
Açıkçası unuttuğum önemli bir gelişme
Bard'ın derleyicisini kontrol ederken, hızı optimize etmek için derleyici anahtarını kullanmadığımı fark ettim! Bu yüzden derleyiciye -Ofast-march = native -mtune = native -funroll-döngüleri ekledim, bu kadar basit. Tahmin et ne oldu...
Hız 6552 kata, saniyede yaklaşık 30050 şarkıya ve 1000 şarkı için yalnızca 16 saniyeye çıkarıldı.
Ücretsiz Tumbleweed iyileştirmeleri
OpenSUSETumbleweed geliştirme için kullandığım sistemde çalışıyor Muhtemelen çok kullanışlı bir Linux dağıtımı olduğunu biliyorsunuzdur. Bir test yaptığım bir gün, Tumbleweed derleyiciyi gcc 7.3'ten gcc8.1'e güncelledi. Bu yüzden tekrar test etmem gerektiğini düşünüyorum.
Sadece derleyiciyi en son sürüme yükselterek, hız 7714 kata, saniyede 35380 şarkıya ve 1.000 şarkı için yalnızca 14 saniyeye yükseltildi.
Nihai optimizasyon
Henüz yapmadığım çok açık bir optimizasyon, haritayı vektör ile değiştirmektir, böylece her için çağırmadan önce dönüşüm gerçekleştirmeye gerek kalmaz. Dahası, vektör önceden alan tahsis edebilir, tüm algoritmanın sonunda vektörün son boyutunu bildiğim için, önceden alan ayırmak için kodu değiştirdim.
Bu değişiklik bana son hızlanma zamanı verdi. Hız saniyede 36680 şarkı olmak üzere 7998 kata çıkarıldı ve 1000 şarkılık bir kitaplığı tam olarak işlemek yalnızca 13 saniye sürdü.
sonuç olarak
Bu deneyimden kazanılan bazı önemli deneyimler:
- Kodu optimize etmek için zaman ayırın, paraya değer.
- C ++ kullanıyorsanız ve modern bir derleyici kullanabiliyorsanız, çok daha iyi ve daha verimli kod derleyebilen C ++ 17 kullanmanız gerekir. Lambda, yapılandırılmış bağlama, constexpr vb. Okumaya değer.
- Derleyicinin sizin için bazı işler yapmasına izin verin. Herhangi bir zaman harcamanıza gerek yok, kodu optimize edebilir.
- Verileri olabildiğince az kopyalayın veya taşıyın. Bu, hızı yavaşlatır ve çoğu durumda, yalnızca geliştirme başlamadan önce veri yapısını dikkatlice değerlendirerek önlenebilir.
- Mümkünse iplik kullanın.
- Muhtemelen en önemli ders: her şeyi ölçün. Ölçüm yapmadan iyileştirmenin bir yolu yok. (Olabilir, ancak kesin bir sonuca varamazsınız.)
Orijinal: https://antlarr.io/2018/07/optimizing-a-python-application-with-c-code/
Eser sahibi: antlarr
Çevirmen: Crescent Moon, Kurgu: Tu Min
"Belgeler için çağrı"
CSDN halka açık hesabı, "on binlerce teknik insanla büyüme" kavramına bağlıdır. Teknik insanların ilk kez ilgilendikleri endüstri odak olaylarını teknik insanların benzersiz bakış açılarından tanımlamak için yalnızca "inek başlıkları" ve "konuşma" sütunlarını kullanmakla kalmaz, aynı zamanda "Teknoloji Başlıkları" sütunu, sektördeki popüler teknolojilerin ve uygulamaların derinlemesine bir yorumunu sunarak, tüm geliştiricilerin teknolojik trendlere ayak uydurmasına, uyanık bir teknolojik anlayışı sürdürmesine ve sektör eğilimleri ve teknolojileri hakkında daha kapsamlı bir anlayışa sahip olmasına olanak tanır.
Yüksek kaliteli makaleleriniz veya sektörün sıcak olayları, teknoloji trendleri hakkında içgörüler veya derinlemesine uygulama uygulamaları, senaryolar vb. Hakkında yeni içgörüleriniz varsa, gönderimler için lütfen CSDN ile iletişime geçin. İletişim: WeChat (guorui_1118, lütfen gönderim + ad + şirket pozisyonunu not edin), e-posta (guorui@csdn.net).
