فضولي بشأن مشكلات الأداء القابلة للتصنيف

Question

قرأت أن جداول التجزئة في هاسكل لديها مشكلات في الأداء (على Haskell-Cafe في عام 2006 و مدونة Flying Frog Consultancy في عام 2009) ، وبما أنني أحب هاسكل ، فإنني قلقني.

كان ذلك قبل عام ، ما هو الوضع الآن (يونيو 2010)؟ هل تم إصلاح "مشكلة جدول التجزئة" في GHC؟

Answer 1

كانت المشكلة أن جامع القمامة مطلوب لاجتياز صفائف قابلة للتغيير من المؤشرات ("المصفوفات المعبأة") التي تبحث عن مؤشرات للبيانات التي قد تكون جاهزة للتعامل. المصفوفات المعبأة والقابلة للتبديل هي الآلية الرئيسية لتنفيذ علامة تصنيف ، بحيث أظهر بنية معينة مشكلة اجتياز GC. هذا شائع في العديد من اللغات. الأعراض هي جمع القمامة المفرطة (ما يصل إلى 95 ٪ من الوقت الذي يقضيه في GC).

كان الإصلاح تنفيذ "علامة البطاقة" في GC بالنسبة إلى المصفوفات القابلة للتغيير من المؤشرات ، التي حدثت في أواخر عام 2009. يجب ألا ترى GC المفرط عند استخدام صفائف قابلة للتغيير من المؤشرات في Haskell الآن. على المعايير البسيطة ، تم تحسين الإدراج القابل للتجزئة للتجزئة الكبيرة بمقدار 10x.

لاحظ أن مشكلة المشي GC لا تؤثر الهياكل الوظيفية البحتة, ، ولا صفائف غير مربعة (مثل معظم البيانات صفائف موازية, ، أو المتجه-مثل المصفوفات ، في هاسكل. كما أنه لا يؤثر على علامات التجزئة المخزنة على كومة C (مثل جودي). وهذا يعني أنه لم يؤثر على haskellers اليومية الذين لا يستخدمون جداول التجزئة الضرورية.

إذا كنت تستخدم علامات التجزئة في Haskell ، فلا يجب عليك ملاحظة أي مشكلة الآن. هنا ، على سبيل المثال ، هو برنامج علامة تصنيف بسيطة يقوم بإدراج 10 ملايين INTs في تجزئة. سأقوم بالقياس ، لأن الاقتباس الأصلي لا يقدم أي رمز أو معايير.

import Control.Monad
import qualified Data.HashTable as H
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  m <- H.new (==) H.hashInt
  forM_ [1..size] $ \n -> H.insert m n n
  v <- H.lookup m 100
  print v

مع GHC 6.10.2 ، قبل الإصلاح ، إدراج 10 أمتار:

$ time ./A 10000000 +RTS -s
...
47s.

مع GHC 6.13 ، بعد الإصلاح:

./A 10000000 +RTS -s 
...
8s

زيادة منطقة الكومة الافتراضية:

./A +RTS -s -A2G
...
2.3s

تجنب علامات التجزئة واستخدام intmap:

import Control.Monad
import Data.List
import qualified Data.IntMap as I
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  let k = foldl' (\m n -> I.insert n n m) I.empty [1..size]
  print $ I.lookup 100 k

ونحصل على:

$ time ./A 10000000 +RTS -s        
./A 10000000 +RTS -s
6s

أو بدلاً من ذلك ، باستخدام مجموعة جودي (وهو عبارة عن رمز Class Class Class Class من خلال واجهة الوظيفة الأجنبية):

import Control.Monad
import Data.List
import System.Environment
import qualified Data.Judy as J

main = do
  [size] <- fmap (fmap read) getArgs
  j <- J.new :: IO (J.JudyL Int)
  forM_ [1..size] $ \n -> J.insert (fromIntegral n) n j
  print =<< J.lookup 100 j

تشغيل هذا ،

$ time ./A 10000000 +RTS -s
...
2.1s

لذلك ، كما ترون ، فإن مشكلة GC مع علامات التجزئة مُثَبَّت, ، وهناك كانت دائمًا المكتبات وهياكل البيانات الأخرى التي كانت مناسبة تماما. باختصار ، هذا ليس قضية.

ملاحظة: اعتبارًا من عام 2013 ، ربما يجب عليك فقط استخدام علامات الهاش الحزمة ، التي تدعم مجموعة من علامات التجزئة القابلة للتغيير نا.

Answer 2

لا يمكن تسوية سؤال مثل هذا إلا عن طريق التجربة. ولكن إذا لم يكن لديك الوقت أو المال لإجراء تجارب ، فعليك أن تسأل الآخرين عن رأيهم. عندما تفعل ذلك ، قد ترغب في التفكير في المصدر والنظر في ما إذا كانت المعلومات المقدمة قد تمت مراجعتها أو فحصها بأي شكل من الأشكال.

قام جون هاروب بتطوير بعض المطالبات المثيرة للاهتمام حول هاسكل. اسمحوا لي أن أقترح عليك البحث في مجموعات Google وأماكن أخرى عن أدلة على خبرة Harrop في Haskell و Lisp ولغات وظيفية أخرى. يمكنك أيضًا قراءة عمل كريس أوكاساكي وأندي جيل على أشجار باتريشيا في هاسكل ، انظر كيف يتم اعتبار خبرتهم. يمكنك أيضًا العثور على مطالباتهم ، إن وجدت ، تم فحصها من قبل طرف ثالث. بعد ذلك ، يمكنك أن تعوض عن عقلك مدى جدية في أخذ مطالبات الأشخاص المختلفين حول أداء اللغات الوظيفية المختلفة.

أوه ، ولا تغذي القزم.

---

ملاحظة: سيكون من المنطقي بالنسبة لك إجراء تجاربك الخاصة ، ولكن ربما ليس ضروريًا ، منذ الوثوق يقدم دون ستيوارت بعض العلامات الدقيقة اللطيفة في إجابته الجميلة. إليك إضافة لإجابة دون:

---

إضافة: استخدام رمز Don Stewart على إصدار AMD Phenom 9850 الأسود الذي تم تسجيله عند 2.5 جيجا هرتز مع ذاكرة الوصول العشوائي 4 جيجابايت ، في وضع 32 بت ، مع ghc -O,

• مع الكومة الافتراضية ، IntMap هو 40 ٪ أسرع من جدول التجزئة.
• مع كومة 2G ، يكون جدول التجزئة أسرع بنسبة 40 ٪ من IntMap.
• إذا ذهبت إلى عشرة ملايين عنصر مع الكومة الافتراضية ، IntMap هو أربع مرات أسرع من جدول التجزئة (وقت وحدة المعالجة المركزية) أو مرتين بسرعة بحلول وقت الحائط.

أنا مندهش قليلاً من هذه النتيجة ، لكنني طمأنت أن هياكل البيانات الوظيفية تعمل بشكل جيد. وتأكيدًا في اعتقادي أنه من المفيد حقًا تحديد رمزك في ظل الظروف الفعلية التي سيتم استخدامها فيها.

Answer 3

باختصار ، حتى مع الإصلاح في أحدث GHC ، لا يزال Haskell غير قادر على توفير القاموس (قابلاً للتغيير أو غير قابل للتغيير) الذي يكون فعالًا بشكل تنافسي.

كانت طاولات التجزئة Haskell 32 × أبطأ من بدائل مثل C ++ و .NET مع GHC 6.10. كان ذلك يرجع جزئيًا إلى ملف علة الأداء في جامع القمامة GHC الذي تم إصلاحه لـ GHC 6.12.2. لكن نتائج Simon Marlow لا تظهر سوى تحسين الأداء 5 × لا يزال يترك جداول هاش هاسيل أبطأ عدة مرات من معظم البدائل.

البدائل الوظيفية البحتة هي أيضا أبطأ بكثير من جدول التجزئة لائق. فمثلا، هاسكل IntMap هو 10 × أبطأ من جدول التجزئة .NET.

باستخدام F# 2010 و أحدث منصة هاسكل 2010.2.0.0 (تم إصداره بالأمس!) مع GHC 6.12.3 على هذا 2.0 جيجا هرتز E5405 Xeon يعمل بنظام التشغيل Windows 32 بت لإدراج روابط 20 مترًا int-> في جدول تجزئة فارغ نجد أن Haskell لا يزال 29 × أبطأ من F# في الوقت الحقيقي و أكثر من 200 × أبطأ من حيث وقت وحدة المعالجة المركزية لأن هاسكل يحرق جميع النوى:

GHC 6.12.3 Data.HashTable: 42.8s (new!)
.NET hash table:            1.47s

شريطة تشغيل علامات Microbenchles قصيرة العمر فقط يمكنك تعطيل جامع GHC القمامة كما يوحي دون ستيوارت أعلاه. من خلال طلب جيل حضانة كبيرًا لدرجة أن هذا البرنامج بالذات لن يملأه أبدًا ، فقد أحضر الوقت لجدول Haskell Hash إلى 1.5 ثانية فقط. ومع ذلك ، فإن هذا يقوض تمامًا بيت القصيد من وجود جيل حضانة وسيؤدي إلى تدهور أداء التعليمات البرمجية الأخرى بشكل كبير لأن القيم المخصصة حديثًا ستكون دائمًا باردة في ذاكرة التخزين المؤقت (وهذا هو السبب في أن توليد الحضانة عادة ما يكون حجم ذاكرة التخزين المؤقت L2 ، أوامر حجم أصغر من هذا).