Все потоки
Поиск
Написать публикацию
Обновить

Комментарии 34

Решая задачки на hackerrank, я тоже заметил, что ввод-вывод в D работает ощутимо шустрее, чем в C++.

Однако, кажется, в вашей C++-реализации происходит довольно много лишней работы.

Вместо

vector<Measure> readMeasuresFromFile( char* name )
{
    ifstream file( name );
    vector<Measure> list;

    for( string line; getline(file, line); )
    {
        istringstream in( line );
        Measure tmp;
        in >> tmp.x >> tmp.y;
        list.push_back( tmp );
    }

    return list;
}


Вполне можно было написать что-то вроде

vector<Measure> readMeasuresFromFile( const char* name )
{
    ifstream file( name );
    vector<Measure> list;
    Measure tmp;
    while (file >> tmp.x)
    {
        file >> tmp.y;
        list.push_back( tmp );
    }

    return list;
}


Так можно избежать большого количества копий строк.
Рейтинг скрыт
Согласен, мой косяк.
Рейтинг скрыт
Просто ifstream — не лучшее решение, если нужна максимальная скорость работы с вводом/выводом.
Рейтинг скрыт
> Просто ifstream — не лучшее решение, если нужна максимальная скорость работы с вводом/выводом

Это верно. На игрушечных задачках я в основном использовал cin/cout с sync_with_stdio(false).

На хабре уже было исследование на эту тему. Старый добрый <cstdio> быстр, но не всегда удобен на практике.

std.stdio в D мне нравится одновременно простотой и эффективностью. Не нужно думать, где сколько букв l нужно писать в строке формата, компилятор сам может вставить правильный код. Ну и он бросает исключения в случае ошибок, не нужно смотреть коды возврата / флажки.
Рейтинг скрыт
НЛО прилетело и опубликовало эту надпись здесь
Возможно, а что сейчас принято использовать на С++ для ввода?
Рейтинг скрыт
Большинству хватает fstream — редко когда нужна максимальная скорость ввода вывода файлов. Кому нужна — есть много альтернативных библиотек, вроде даже тот же QFile быстрее. Ну и пишут свои велосипеды с системными read()/write()
Рейтинг скрыт
НЛО прилетело и опубликовало эту надпись здесь
Не сталкивались ли с какими-либо косяками при использовании не-dmd компилятора?
Рейтинг скрыт
Единственный косяк, который мне приходилось отлавливать не косяк по сути. Версия dmd всегда свежее версий frontend'ов gdc и ldc2. Но dmd я пользуюсь как основным, так что не могу полностью гарантировать, что их нет.
Рейтинг скрыт
НЛО прилетело и опубликовало эту надпись здесь
deviator а не могли бы вы предоставить сгенерированную выборку? К сожалению, нет возможности сгенерировать выборку с помощью вашего генератора на D. Но есть интерес в реализации алгоритма на Rust.

PS: думаю Rust будет немного медленее, чем C++ из-за безопасности кода
Рейтинг скрыт
Было бы очень классно. Выборку я думаю всю предоставлять не имеет смысла, во-первых из-за того, что она 74Мб, во-вторых из-за того, что она тривиальна: 3 набора 2-мерных точек, каждый из которых это реализация нормального распределения с заданным мат. ожиданием и дисперсией (на картинке в начале). Точки в файл записаны в случайном порядке. Мат. ожидания и количество точек задаются в функции main генератора.
небольшой фрагмент выборки
-4.67215 -8.07063
-6.56169 -7.13031
-5.94033 -7.09787
-6.47569 -7.6819
-7.40864 -7.69549
-6.89396 -8.54811
-5.08555 -6.72476
-5.13537 -8.38572
-5.59292 -7.04139
-5.62399 -8.811
-6.64349 -7.68353
-6.42634 -9.9467
-7.0504 -8.40296
-4.95483 -9.32353
-4.46654 -9.13888
-8.7821 10.3502
-7.89502 7.76488
-8.334 8.59684
-8.47567 8.01326
-8.11803 9.81281
-8.74283 8.56988
-7.37152 6.98727
-7.24001 7.85616
-6.90632 8.52209
-7.86361 6.87816
-7.54269 6.49742
-8.38692 7.54622
-8.26923 9.62765
-10.4273 7.98343
-6.39929 7.61442
-8.49307 7.86102
-9.80588 8.37838
-7.35485 5.89452
-8.84699 7.78655
-8.74931 9.02794
3.51376 -0.501566
4.47393 -0.988967
2.29637 -0.731235
4.14499 -1.06795
3.62683 -1.55822
4.29838 1.80077
4.33734 -0.0835588
4.81545 -0.525413
4.64983 0.865473
4.77081 -0.460162
Рейтинг скрыт
Выложите, может быть, всё-таки ваш набор, для честности эксперимента? :)
Или, по крайней мере, скажите, с каким --count-multiplier вызывался генератор выборки.
А я тоже попробую написать версию на Rust.
Рейтинг скрыт
Ладно, методом тыка обнаружилось, что --count-multiplier ≈ 100k. :)
Рейтинг скрыт
да, ровно 100000
Рейтинг скрыт
С настройками как у вас, у меня получается ≈54 класса с кол-вом точек от 1 до 342k в каждом из классов. Так и должно быть?
Рейтинг скрыт
Добавил слияние классов:

work time: 678 ms
 1 [ -6.000168,  -8.001228]:  500000
 2 [ -8.000780,   7.999724]: 1999999
 3 [  3.999540,   0.001314]: 1000000
 4 [ -5.164976,   2.950943]:       1
Одна точка куда-то упрыгала. :/

Исходники:
sample-generator — github.com/miot/rust-sample-generator
classifier — github.com/miot/rust-classifier
Рейтинг скрыт
тов I_AM_FAKE напсал намного раньше чем Вы, просто я смог выложить это только сейчас. И у Вас нет сохранения набора точек в классах.
Рейтинг скрыт
Да мне не жалко.

Сохранения набора точек действительно пока нет.

Потестировал код на C++ (компилятор VC14). Чтение файла почему-то неимоверно долгое, я не особо умею в C++, не знаю, почему так:

> Measure-Command { .\classifier.exe | Out-Default }

work time: 0.763
[-6.47555, -8.13266]: 86511
[-7.83235, 7.7918]: 342133
[3.79797, 0.0411202]: 183674
[-5.38868, -8.48608]: 73634
...

Days              : 0
Hours             : 0
Minutes           : 1
Seconds           : 13
Milliseconds      : 321
Ticks             : 733214153
TotalDays         : 0.000848627491898148
TotalHours        : 0.0203670598055556
TotalMinutes      : 1.22202358833333
TotalSeconds      : 73.3214153
TotalMilliseconds : 73321.4153

Непосредственно классификация на C++ оказалась медленнее (и это без слияния!). Хотя я уверен, что можно ускориться.
Рейтинг скрыт
да, так и должно быть
Рейтинг скрыт
Rust версия: github.com/biziwalker/rust-habr261201 на предоставленной выборке из 45 позиций

% g++ -std=c++11 -O3 -o ./target/release/cpp-habr ./src/main.cpp
% cargo build --release
% ./target/release/rust-habr input.txt
work time: PT0.000006164S
[-5.928793, -8.112186]: 15
[-8.200232, 8.078455]: 20
[4.092769, -0.32508284]: 10
% ./target/release/cpp-habr input.txt
work time: 1.8e-05
[-5.92879, -8.11219]: 15
[-8.20023, 8.07845]: 20
[4.09277, -0.325083]: 10

Рейтинг скрыт
Получается Rust оказался почти в 3 раза быстрее C++ — что-то здесь не чисто! Код на C++ приводил к индентичному на Rust, единственное это я не реализовал ту фичу заложенную автором, которая включается с помощью #define COLLECT_MEASURES. А так на равных условиях, с отключенными фичами, Rust оказался быстрее. И всетаки надо сравнивать на одинаковом железе и с нормальными выборками. Предлагаю автору ( deviator ) этим заняться и сделать свои выводы кто кого быстрее в этой гонке.
Рейтинг скрыт
на большой выборке Rust всё равно победил)
Рейтинг скрыт
«безопасность» кода в Rust проверяется на стадии компиляции, что никак не отражается на эффективности конечного бинарника.
Рейтинг скрыт
Всего не знаю, но, мне кажется, что на C++ вообще нет такой безопасности.
Рейтинг скрыт
Сталкивался на простых тестах сортировки с тем, что в Rust есть инструкции проверки на доступность элемента в массиве. Скорость просела в 1.5 раза по сравнению с C на сортировке вставками. Но благо Rust позволяет писать unsafe код, если хочется выжить максимум :)
Рейтинг скрыт
Решил поиграться с Haskell.

Платформа: Fedora 21 x64
Входная выборка получена генератором с параметром `100000`.

DMD 2.067.1: 2.85267 s
GHC 7.8.4 (обычный бекэнд): 2.462 s
GHC 7.8.4 (llvm): 2.382 s

Main.hs
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE BangPatterns, MultiParamTypeClasses, TypeFamilies, FlexibleContexts #-}
module Main where 

import Criterion
import Criterion.Main
import Control.DeepSeq
import GHC.Generics (Generic)
import qualified Data.ByteString.Char8 as BS
import qualified Data.Vector.Unboxed as V
import Data.ByteString.Read
import Data.Maybe

import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as M
import Control.Monad 

data Measure = Measure {-# UNPACK #-} !Float {-# UNPACK #-} !Float
  deriving (Generic)

instance NFData Measure 

instance Num Measure where 
  (Measure x1 y1) + (Measure x2 y2) = Measure (x1+x2) (y1+y2)
  (Measure x1 y1) - (Measure x2 y2) = Measure (x1-x2) (y1-y2)
  (Measure x1 y1) * (Measure x2 y2) = Measure (x1*x2) (y1*y2)
  abs = undefined
  signum = undefined
  fromInteger i = Measure (fromIntegral i) (fromIntegral i)

instance Fractional Measure where 
  (Measure x1 y1) / (Measure x2 y2) = Measure (x1/x2) (y1/y2)
  fromRational = undefined

sqr :: Float -> Float 
sqr x = x*x

dist :: Measure -> Measure -> Float 
dist (Measure x1 y1) (Measure x2 y2) = sqrt $ sqr (x1 - x2) + sqr (y1 - y2)

data Class = Class !Measure !Int 
  deriving (Generic)

instance NFData Class 

instance Show Class where
  show (Class (Measure x y) i) = "[" ++ show x ++ ", " ++ show y ++ "]: " ++ show i 

newClass :: Measure -> Class 
newClass m = Class m 1 

append :: Class -> Measure -> Class
append (Class mean n) m = Class newMean (n+1)
  where newMean = ( mean * fromIntegral n + m ) / fromIntegral ( n + 1 )

merge :: Class -> Class -> Class 
merge (Class mean1 n1) (Class mean2 n2) = Class mean3 (n1+n2)
  where mean3 =  ( mean1 * fromIntegral n1 + mean2 * fromIntegral n2 ) / fromIntegral ( n1 + n2 );

classificate :: Float -> V.Vector Measure -> V.Vector Class
classificate nclsDist ms = V.foldl' go V.empty ms 
  where 
    go :: V.Vector Class -> Measure -> V.Vector Class
    go acc m 
      | V.null acc = V.singleton $ newClass m
      | otherwise = if minDist < nclsDist
        then newCls
        else (newClass m) `V.cons` newCls
      where 
        newCls = acc `V.unsafeUpd` [(nearClsI, nearCls `append` m)]
        (nearCls, nearClsI, minDist) = sortByDist acc m

    sortByDist :: V.Vector Class -> Measure -> (Class, Int, Float)
    sortByDist cs m = out $ V.ifoldl' checkDist (0, maxFloat) cs 
      where 
        maxFloat :: Float 
        maxFloat = 1/0

        out :: (Int, Float) -> (Class, Int, Float)
        out (i, d) = (V.unsafeIndex cs i, i, d)

        checkDist :: (Int, Float) -> Int -> Class -> (Int, Float)
        checkDist acc@(_, mdist) i (Class mean _) = if curDist < mdist 
          then (i, curDist)
          else acc
          where curDist = dist m mean

readMeasures :: BS.ByteString -> V.Vector Measure
readMeasures = V.fromList . catMaybes . fmap (go . BS.words) . BS.lines
  where go [a, b] = do
          (x, _) <- signed fractional a
          (y, _) <- signed fractional b 
          return $!! Measure x y
        go _ = Nothing
        
main :: IO ()
main = defaultMain [
    env (fmap readMeasures $ BS.readFile "data") $ \measures ->
      bench "classificate" $ nf (classificate 3) measures
  ]

-- | Алтернативная main функция для проверки правильности реализации
main2 :: IO ()
main2 = do 
  measures <- fmap readMeasures $ BS.readFile "data"
  print $ measures `deepseq` V.length measures
  let classes = classificate 3 measures
  print $ classes `deepseq` V.length classes 
  putStrLn $ unlines $ fmap show $ V.toList classes

-- | Далее идет boilerplate для реализации Unboxed векторов для кастомных типов

newtype instance V.MVector s Measure = MV_Measure (V.MVector s (Float,Float))
newtype instance V.Vector    Measure = V_Measure  (V.Vector    (Float,Float))

instance V.Unbox Measure

instance M.MVector V.MVector Measure where
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicOverlaps #-}
  {-# INLINE basicUnsafeNew #-}
  {-# INLINE basicUnsafeReplicate #-}
  {-# INLINE basicUnsafeRead #-}
  {-# INLINE basicUnsafeWrite #-}
  {-# INLINE basicClear #-}
  {-# INLINE basicSet #-}
  {-# INLINE basicUnsafeCopy #-}
  {-# INLINE basicUnsafeGrow #-}
  basicLength (MV_Measure v) = M.basicLength v
  basicUnsafeSlice i n (MV_Measure v) = MV_Measure $ M.basicUnsafeSlice i n v
  basicOverlaps (MV_Measure v1) (MV_Measure v2) = M.basicOverlaps v1 v2
  basicUnsafeNew n = MV_Measure `liftM` M.basicUnsafeNew n
  basicUnsafeReplicate n (Measure x y) = MV_Measure `liftM` M.basicUnsafeReplicate n (x,y)
  basicUnsafeRead (MV_Measure v) i = uncurry Measure `liftM` M.basicUnsafeRead v i
  basicUnsafeWrite (MV_Measure v) i (Measure x y) = M.basicUnsafeWrite v i (x,y)
  basicClear (MV_Measure v) = M.basicClear v
  basicSet (MV_Measure v) (Measure x y) = M.basicSet v (x,y)
  basicUnsafeCopy (MV_Measure v1) (MV_Measure v2) = M.basicUnsafeCopy v1 v2
  basicUnsafeMove (MV_Measure v1) (MV_Measure v2) = M.basicUnsafeMove v1 v2
  basicUnsafeGrow (MV_Measure v) n = MV_Measure `liftM` M.basicUnsafeGrow v n

instance G.Vector V.Vector Measure where
  {-# INLINE basicUnsafeFreeze #-}
  {-# INLINE basicUnsafeThaw #-}
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicUnsafeIndexM #-}
  {-# INLINE elemseq #-}
  basicUnsafeFreeze (MV_Measure v) = V_Measure `liftM` G.basicUnsafeFreeze v
  basicUnsafeThaw (V_Measure v) = MV_Measure `liftM` G.basicUnsafeThaw v
  basicLength (V_Measure v) = G.basicLength v
  basicUnsafeSlice i n (V_Measure v) = V_Measure $ G.basicUnsafeSlice i n v
  basicUnsafeIndexM (V_Measure v) i
                = uncurry Measure `liftM` G.basicUnsafeIndexM v i
  basicUnsafeCopy (MV_Measure mv) (V_Measure v)
                = G.basicUnsafeCopy mv v
  elemseq _ (Measure x y) z = G.elemseq (undefined :: V.Vector Float) x
                       $ G.elemseq (undefined :: V.Vector Float) y z



newtype instance V.MVector s Class = MV_Class (V.MVector s (Float, Float, Int))
newtype instance V.Vector    Class = V_Class  (V.Vector    (Float, Float, Int))

instance V.Unbox Class

instance M.MVector V.MVector Class where
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicOverlaps #-}
  {-# INLINE basicUnsafeNew #-}
  {-# INLINE basicUnsafeReplicate #-}
  {-# INLINE basicUnsafeRead #-}
  {-# INLINE basicUnsafeWrite #-}
  {-# INLINE basicClear #-}
  {-# INLINE basicSet #-}
  {-# INLINE basicUnsafeCopy #-}
  {-# INLINE basicUnsafeGrow #-}
  basicLength (MV_Class v) = M.basicLength v
  basicUnsafeSlice i n (MV_Class v) = MV_Class $ M.basicUnsafeSlice i n v
  basicOverlaps (MV_Class v1) (MV_Class v2) = M.basicOverlaps v1 v2
  basicUnsafeNew n = MV_Class `liftM` M.basicUnsafeNew n
  basicUnsafeReplicate n (Class (Measure x y) ni) = MV_Class `liftM` M.basicUnsafeReplicate n (x,y,ni)
  basicUnsafeRead (MV_Class v) i = (\(x,y,ni)->Class (Measure x y) ni) `liftM` M.basicUnsafeRead v i
  basicUnsafeWrite (MV_Class v) i (Class (Measure x y) ni) = M.basicUnsafeWrite v i (x,y, ni)
  basicClear (MV_Class v) = M.basicClear v
  basicSet (MV_Class v) (Class (Measure x y) ni) = M.basicSet v (x,y,ni)
  basicUnsafeCopy (MV_Class v1) (MV_Class v2) = M.basicUnsafeCopy v1 v2
  basicUnsafeMove (MV_Class v1) (MV_Class v2) = M.basicUnsafeMove v1 v2
  basicUnsafeGrow (MV_Class v) n = MV_Class `liftM` M.basicUnsafeGrow v n

instance G.Vector V.Vector Class where
  {-# INLINE basicUnsafeFreeze #-}
  {-# INLINE basicUnsafeThaw #-}
  {-# INLINE basicLength #-}
  {-# INLINE basicUnsafeSlice #-}
  {-# INLINE basicUnsafeIndexM #-}
  {-# INLINE elemseq #-}
  basicUnsafeFreeze (MV_Class v) = V_Class `liftM` G.basicUnsafeFreeze v
  basicUnsafeThaw (V_Class v) = MV_Class `liftM` G.basicUnsafeThaw v
  basicLength (V_Class v) = G.basicLength v
  basicUnsafeSlice i n (V_Class v) = V_Class $ G.basicUnsafeSlice i n v
  basicUnsafeIndexM (V_Class v) i
                = (\(x,y,ni)->Class (Measure x y) ni) `liftM` G.basicUnsafeIndexM v i
  basicUnsafeCopy (MV_Class mv) (V_Class v)
                = G.basicUnsafeCopy mv v
  elemseq _ (Class (Measure x y) ni) z = G.elemseq (undefined :: V.Vector Float) x
                       $ G.elemseq (undefined :: V.Vector Float) y 
                       $ G.elemseq (undefined :: V.Vector Int) ni z



Cabal файл
name:                cls-bench
version:             0.1.0.0
license:             BSD3
license-file:        LICENSE
author:              Anton Gushcha
maintainer:          ncrashed@gmail.com
build-type:          Simple
cabal-version:       >=1.10

executable cls-bench
  main-is:             Main.hs
  build-depends:       base >= 4.7, criterion >= 1.1, deepseq, bytestring >= 0.10, bytestring-read >= 0.3, vector
  default-language:    Haskell2010
  ghc-options:         -O2 -threaded

Рейтинг скрыт
С моей точки зрения, заголовок некорректен.
В данном конкретном случае нужно говорить не о сравнении языков, а о сравнении скорости функций ввода-вывода двух конкретных реализаций библиотек. Это по большей части.
Являясь профессионалом в D, вы подготовили сравнительно оптимальный код D и «просто работающий» код С++. После чего получили те результаты, которые получили. Что они действительно показывают — вопрос отдельный. Но уж точно не «сравнение производительности двух языков».
Рейтинг скрыт
а о сравнении скорости функций ввода-вывода двух конкретных реализаций библиотек
Таблица в статье не включает ввод-вывод.
Рейтинг скрыт
К сожалению, автор не привёл профилирование версии без ввода-вывода, но судя по результатам общего профилирования, в версии для С++ не связанные с парсингом файла вызовы даже не попали на первую страницу. Всё что мы там видим — это библиотечные вызовы и загрузка данных. Единственный вопрос вызвал dynamic_cast, но его нет и в исходниках автора.
А вот интересующие нас вызовы в D вполне заметны по времени, начинаясь примерно с 5,8%.
То есть сравнение «мутное» даже без парсинга файла. Почему? Надо разбираться. Я навскидку скажу, что очень много new/delete вызовов в цикле. То есть мы по сути тестируем скорость менеджера памяти для конкретной реализации runtime library С++. Стандартный менеджер, действительно, не самый быстрый. Я, например, пользуюсь фреймворком U++, где этот менеджер по умолчанию свой, более быстрый.
В D тоже может быть более эффективный менеджер памяти, особенно вкупе с необходимостью иметь быстрый мусоросборщик.
Но это лишь предположение — чтобы сказать точно, нужно профилировать версии без парсинга.
Рейтинг скрыт
Как-то раз в бородатом детстве в 1993-ом кажется году мы решили писать компьютерную игрушку и для этого решили сравнить производительность трёх языков, на которых умели писать. Borland C++ 4.0, Turbo Pascal 7.0 и Fortran 77. Тестировались две нужные нам задачи — Умножение вектора на матрицу и отрисовывание треугольника стандартными инструментами в режиме EGA.

Довольно быстро выяснилось, что рисование у C и Pascal шло с одинаковой скоростью, потому как использовало одну и ту же библиотеку egavga.bgi, Расчёты на С были примерно вдвое быстрее, за счёт разнообразных проверок на переполнение, которые в Паскале по умолчанию были включены, а в C по умолчанию выключены. Но это можно было исправить директивами компилятора. А вот с фортраном началось самое интересное:

Первый замер был про умножение на матрицу. Когда фортран показал результат в 10000 раз быстрее у нас закралось подозрение. Сначала мы пытались найти ошибку, но потом сдались. Дизасемблирование показало, что отимизатор смекнул, что результаты вычислений внутри цикла не используются и посчитал умножения и суммирования только один раз, для значения переменной цикла в последнем цикле.

Тогда вместо того чтобы внутри цикла делать просто умножения и сложения мы заставили его ещё и суммировать переменную цикла. Когда фортран показал результаты в 10000 раз быстрее, мы сразу полезли в дизасемблер и к величайшему нашему удивлению обнаружили, что фортран суммирование переменной цикла в цикле успешно заменил на формулу подсчёта арифметической прогрессии. Сказать, что мы были в шоке — ничего не сказать.

Следующие пол часа ушли на подбор такой формулы для замеров, в которой оптимизатор фортрана ничего не смог бы упростить. Задачка оказалось нетривиальной, потому что на глазах у удивлённых школьников фортран выносил общий множитель за скобку, заранее умножал друг на друга константы и делал ещё несколько не менее интеллектуальных операций потрясая наше воображение. Когда мы таки смогли его обмануть выяснилось, что по скорости он от C по скорости не отличается.

Когда мы заставили фортран нарисовать закрашенный треугольник 256 цветами, и он показал результаты ровно в 16 раз лучше egavga.bgi мы уже даже не удивились. В EGA было всего 16 цветов. Рисование цветом 17 было то же самое, что рисование цветом 1. Уж не знаю как Fortran77 дозрел до этой идеи, но он треугольник перерисовал только 16 раз разными цветами, и на этом покинул цикл. Пришлось каждый следующий треугольник рисовать сдвигая одну из вершин на 1 пиксель. Результаты оказались примерно такие же как у конкурентов.

В общем по результатам всей этой истории у меня осталось два выводы:
1) Нет большой разницы на каком из нормальных компиляторов писать, если не лениться.
2) Оптимизатор в фортране написан сошедшими на землю богами.
Рейтинг скрыт
Особенно верно, если учесть, что у большинства современных языков на бэкенде LLVM или GCC
Рейтинг скрыт
Для чистоты эксперимента надо было C++ компилировать clang'ом.
Рейтинг скрыт
Зарегистрируйтесь на Хабре, чтобы оставить комментарий

Публикации

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2026, Habr