?

Log in

No account? Create an account
Дважды мудак [entries|archive|friends|userinfo]
Декларативное рулит

Site Meter

[ website | Мой сайт ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Загадка на ночь этап 2 - итоги [дек. 25, 2012|22:19 pm]
Andy Melnikov
[Tags|, , ]

Обнаружил тут, что в прошлых тестах использовал файл, нечестно полученный трехкратным склеиванием "настоящего". Сейчас перетестирую на 1/3. Надо будет честный предельный файл с 6 млн строк раздобыть

Условие: дан CSV-файд 1.7 млн строк, 248МБ. Тест на непустоту проходят 1.1 млн строк, 34МБ ключей. Надо побить строки на поля через запятую, взять поля с индексами 4 и 15, слепить из них составной ключ и посчитать, сколько разных комбинаций.

FileCommit, MBCPU, s
intrusive.cpp643
csvreader-pypy.py1208 (!)
2-tokenize.js1208 (!)
2.pl13030
Some41-ht-ffi.hs16213
Some41-ffi.hs2018
a_tokenize.java2808
2.sh?21


Аутсайдеры (для истории):

FileCommit, MBCPU, s
2-arena-stdio.cpp803
2-cpp-arena-2.cpp808
2-getline.js12011
2.js12023
vsh-arena-ht.hs 19013
a-dirty.java28010
Some41-2.hs2609
Some41-3.hs2808
Some41-5.hs28018
Some41.hs58510


Мерял градусником, важен порядок величины (но при повторных запусках рез-ты не меняются). В-общем, 260/9 is good enough for production use, требования у меня уложиться в 5 мбайт/сек и 2 гб при задействовании 4 ядер, а здесь всего 1 ядро, которое, к тому же, медленнее, чем продакшен-процессоры. Памяти больше чем 2 гб, но она съедена другими компонентами.

Осталось что-нибудь из http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-libraries/ через FFI прикрутить :-\ Ещё подсказывают http://judy.sourceforge.net/doc/JudySL_3x.htm

А вот специфичное для х-я: http://www.haskell.org/haskellwiki/Shootout/Knucleotide . Интересно, что на шутауте Хаскель по памяти проигрывает state of the art C++ безбожно (400 vs 130)

Upd: я тут ускорил ноуд, до 11s.

Теперь v8 обгоняет ghc, внезапно. Вариант с малым потреблением памяти, конечно. Учитывая что сделано через сплит - скорость такая же, как у варианта Java со split, что снова неожиданно. Делаю кастомный токенизатор.

Upd2: ускорил до 8с

Upd3: http://nponeccop.livejournal.com/305014.html - новый алгоритм с потенциалом чудовищно сократить память!

Upd4: Cтарый алгоритм, но хеш из буста - 64М. По времени тоже быстрее, если мерять точно павершеллом. И ещё один бенчмарк хеш-таблиц.
СсылкаОтветить

Comments:
[User Picture]From: theiced
2012-12-25 10:18 pm
а можно файлик тестовый, а.
(Ответить) (Thread)
[User Picture]From: theiced
2012-12-25 10:19 pm
ну то есть хаскель говно же тормозное, уверен что можно на чём нить хорошем и быстро.
(Ответить) (Parent) (Thread) (Развернуть)
(Скрытый комментарий)
[User Picture]From: some41
2012-12-26 04:57 am
написал короткую строку. думаю должно быть сравнимо по памяти с динамическими языками.
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE MagicHash, ForeignFunctionInterface, UnboxedTuples, BangPatterns, UnliftedFFITypes #-}
import qualified Data.HashMap.Strict as HM
import Control.Monad
import qualified Data.ByteString.Char8 as B
import qualified Data.ByteString.Lazy.Char8 as BL

import qualified Data.ByteString.Internal as BI
import GHC.Base (Int(..), ByteArray#, MutableByteArray#, newByteArray#, sizeofByteArray#, unsafeFreezeByteArray#, (==#))
import GHC.ST (ST(..), runST)
import Control.Monad.ST.Unsafe
import Foreign.ForeignPtr       (withForeignPtr)
import Foreign.Ptr              (Ptr, plusPtr)
import Foreign.C.Types          (CInt(..), CSize(..))
import Data.Word
import Data.Hashable

data ShortStr = ShortStr ByteArray#

instance Eq ShortStr where
    (ShortStr a1) == (ShortStr a2) = len1 ==# len2 && BI.inlinePerformIO (do i <- memcmp a1 a2 $ fromIntegral (I# len1)
                                                                             return $! i == 0)
                                     where len1 = sizeofByteArray# a1
                                           len2 = sizeofByteArray# a2

instance Hashable ShortStr where
    hash = hash . toBS

fromBS bs = runST $ ST $ \s1 ->
            let !(I# l)         = len
                !(# s2, marr #) = newByteArray# l s1
                !(ST m)         = fill marr
                !(# s3, _ #)    = m s2
                !(# s4, arr #)  = unsafeFreezeByteArray# marr s3
            in (# s4, ShortStr arr #)
    where (ptr, off, len) = BI.toForeignPtr bs
          fill marr       = unsafeIOToST $ withForeignPtr ptr $ \p -> memcpy1 marr (p `plusPtr` off) (fromIntegral len)

toBS (ShortStr arr) = BI.unsafeCreate len $ \p -> memcpy2 p arr (fromIntegral len) >> return ()
    where len = I# (sizeofByteArray# arr)

foreign import ccall unsafe "string.h memcpy" memcpy1
    :: MutableByteArray# s -> Ptr Word8 -> CSize -> IO (Ptr Word8)

foreign import ccall unsafe "string.h memcpy" memcpy2
    :: Ptr Word8 -> ByteArray# -> CSize -> IO (Ptr Word8)

foreign import ccall unsafe "string.h memcmp" memcmp
    :: ByteArray# -> ByteArray# -> CSize -> IO CInt


main = do
    content <- BL.getContents
    let counts = HM.fromListWith (+) [ (fromBS $ B.concat (BL.toChunks x ++ [","] ++ BL.toChunks y), 1)
                                     | line <- map (BL.split ',') $ BL.lines content
                                     , length line > 15
                                     , let x = line!!4, let y = line!!15
                                     , x /= "", y /= "" ]
    mapM_ B.putStrLn [ B.concat [toBS key, ": ", B.pack $ show cnt]
                     | (key, cnt) <- HM.toList counts
                     , cnt > 4 ]
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-26 07:26 am
some41-ffi.hs 201MB 8s

Надо бы http://hackage.haskell.org/package/hashtables попробовать

Edited at 2012-12-26 08:02 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
From: sassa_nf
2012-12-26 07:22 pm
ну на скорую руку (раз джава должна порвать):
import java.io.*;
import java.util.*;
public class a {
  public static void main( String [] args ) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line;
    HashMap<String,Integer> counts = new HashMap<String,Integer>();
    String [] matches = new String[15];
    while( (line = br.readLine()) != null ) {
      StringTokenizer st = new StringTokenizer(line, ",");

      int i;
      for( i = 0; i < matches.length && st.hasMoreTokens(); i++ ) matches[i] = st.nextToken();
      if ( i < matches.length ||
           matches[4].equals("") ||
           matches[15].equals("") ) continue;

      String k = matches[4] + "," + matches[15];
      Integer c = counts.get(k);
      if ( c == null ) counts.put(k, Integer.valueOf(1));
      else counts.put(k, Integer.valueOf(c+1));
    }

    for(Map.Entry<String,Integer> e: counts.entrySet()) if (e.getValue() > 4) {
      System.out.println(e.getKey() + ": " + e.getValue());
    }
  }
}


Edited at 2012-12-26 19:26 (UTC)
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-26 07:36 pm
Вы Jar дайте и запускать научите, у меня JDK нету, но JRE есть.
(Ответить) (Parent) (Thread) (Развернуть)
From: sassa_nf
2012-12-26 10:19 pm
"на шутауте..."

на шутауте ехрня, а не тестирование.
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-26 10:34 pm
Ага. Вот здесь оказывается внезапно, что наивно написанные Х-ь, джава и плюсы идут нос-в-нос, а по памяти их опять же внезапно делают наивные перлы с в8.

Я не говорю, что у меня "тестирование", но код хотя бы немного приближён к жизни. Я надеюсь, что по мере разрастания задачи наивные плюсы отстанут от наивных хаскелей.

Edited at 2012-12-26 22:37 (UTC)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vshabanov
2012-12-27 12:13 am
Попробовал сделать арену для строк на Хаскеле. Интересно, сколько оно памяти теперь кушает?

{-# LANGUAGE OverloadedStrings, BangPatterns #-}
import qualified Data.ByteString.Internal as B
import qualified Data.ByteString.Char8 as B
import qualified Data.ByteString.Lazy.Char8 as BL
import qualified Data.HashMap.Strict as HM
import Control.Monad
import qualified Data.Text as T
import qualified Data.Text.IO as TIO
import qualified Data.Text.Encoding as E
import Foreign.Ptr
import Foreign.ForeignPtr
import Data.Word

data Arena = Arena {-# UNPACK #-} !(Ptr Word8)
                   {-# UNPACK #-} !Int
                   !(ForeignPtr Word8)

arenaSize = 1024*1024

newArena = do
    fp <- B.mallocByteString arenaSize
    withForeignPtr fp $ \ p -> return (Arena p 0 fp)
addToArena bs@(B.PS fp o l) (Arena ap ao afp)
    | ao + l > arenaSize = do
        a <- newArena
        addToArena bs a
    | otherwise = withForeignPtr fp $ \ p -> do
        B.memcpy ap (p `plusPtr` o) (toEnum l)
        return (B.PS afp ao l, Arena (ap `plusPtr` l) (ao+l) afp)
        -- TODO: правильно делать через IORef,
        -- т.к. старая Arena все равно уже ни на что не пригодна
countKeys keys = do
    a <- newArena
    count HM.empty a keys
    where count m _ [] = return m
          count !m !a (k:ks)
              | Just n <- HM.lookup k m = count (HM.insert k (n+1) m) a ks
              | otherwise = do
                  (k', a') <- addToArena k a
                  count (HM.insert k' 1 m) a' ks

main = do
    content <- BL.getContents  -- BL.readFile "test.csv"
    counts <- countKeys
        [ B.concat (BL.toChunks x ++ [","] ++ BL.toChunks y)
        | line <- map (BL.split ',') $ BL.lines content
        , length line > 15
        , let x = line!!4, let y = line!!15
        , x /= "", y /= "" ]
    mapM_ B.putStrLn [ B.concat [key, ": ", B.pack $ show cnt]
                     | (key, cnt) <- HM.toList counts
                     , cnt > 4 ]
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-27 12:21 am
vsh-arena.hs 240 MB 8s

Data.HashTable.IO надо использовать, у Data.HashMap.Strict оверхед больше.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ko_bx
2012-12-27 08:03 am
Раз уж такая пьянка, интересно было бы запустить на python и pypy

https://gist.github.com/4386447

тот, который -cpython лучше обычным питоном запускать, а тот, который -pypy лучше при помощи pypy.

PyPy можно скачать, распаковать и запустить здесь http://buildbot.pypy.org/nightly/trunk/ (-c-latest который).

Спасибо.
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-27 08:17 am
пайпай жжёт, обновил табличку в посте.
(Ответить) (Parent) (Thread) (Развернуть)
(Удалённый комментарий)
[User Picture]From: nponeccop
2012-12-27 12:23 pm
Нет. Ваша программа на шелле не соответствует спецификации. Хотите, можете сделать на шелле, я добавлю в список.
(Ответить) (Parent) (Thread)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
[User Picture]From: livejournal
2012-12-27 01:29 pm

Две вещи.

User thesz referenced to your post from Две вещи. saying: [...] ственная связь "штанга->Хаскель" неверна. Далее, мне очень интересно продолжение вот этой ветви [...]
(Ответить) (Thread)
[User Picture]From: _adept_
2012-12-28 12:42 pm
А как мерялась память?
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-28 12:46 pm
Commit size на глазок в таск менеджере Windows 7. Но Working Set такой же, как коммит сайз у всех.

(Ответить) (Parent) (Thread)
(Удалённый комментарий)
[User Picture]From: _slw
2012-12-28 12:49 pm
должно получиться как минимум говно по скорости и не исключено что по памяти
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: _adept_
2012-12-28 01:15 pm
А вот чистый awk:

awk -F, -vSUBSEP="," '$5!="" && $16!="" {count[$5,$16]+=1} END{for (k in count){if(count[k]>=4){print k}}}'
(Ответить) (Thread)
[User Picture]From: _slw
2012-12-28 03:21 pm
а кстати, если на sql писать -- сколько по времени получается?
для золотой пятерки -- sqlite, mysql, postgres, mssql, oracle.
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-28 04:43 pm
Похуй сколько по времени. Главное по памяти. Есть подозрение, что не поместятся, но проверять лень.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: max has
2012-12-29 07:48 pm

ob hnc

ne sochtite za trola, no hotelos be yvidet HNC v boy.
(Ответить) (Thread)
[User Picture]From: nponeccop
2012-12-29 08:31 pm

Re: ob hnc

Ага, это в планах https://github.com/kayuri/HNC/issues/37
(Ответить) (Parent) (Thread)