Доброго времени суток, хабр!


Моим основным ЯП является D. Всегда понимал, что он будет проигрывать C++ из-за сборщика, каких-то высокоуровневых плюшек и т.д. Но никогда не доходили руки проверить насколько. Решил написать простенький классификатор (даже не помню метод как называется) и проверить. Результат меня приятно удивил: версия C++ отработала за 5.47 сек, версия D — за 5.55 сек. «0.08 сек при обработке файла в 74Мб это не так уж и много» — подумал я. Но, на всякий случай, решил попробовать собрать код на D с помощью gdc (dmd как frontend, gnu backend) и тут уже в душу закрались сомнения, что я всё сделал правильно: код отработал за 4.01 сек, что более чем на 20% быстрее версии на С++. Решил собрать с помощью ldc2 (dmd frontend, llvm backend): 2.92(!!) сек. Тут я решил разобраться.

Первым делом запустил valgrind --tool=callgrind для C++ версии. Как и следовало ожидать на чтение файла уходит бОльшая часть времени.



К сожалению, для версии dmd valgrind не смог отработать и завершился ошибкой illegal hardware instruction, видимо ребята из DigitalMars наколдовали с асемблером сильно, но для gdc и ldc2 всё сработало, как для версии С++.



Хоть и valgrind не demangle'ит имена D функций, зато есть маленький хак: callgrind.out.NNN пропускаем через этот инструмент и получаем нормальные имена (не все, но большую часть). И прошу прощения за gdb, версия 7.9.1-13.fc22 полностью поддерживает demangle D кода.

Осознал я, что рано радоваться, нужно выяснить время выполнения непосредственно алгоритма. И раз уж на то пошло, попробовать различные варианты алгоритма:
  1. минимальный — создаются классификаторы, точки в классах не сохраняются
  2. с сохранением точек и слиянием классов (изначальный алгоритм с изначальной настройкой плодил много классов)

Пара слов по поводу алгоритма: я не ставил задачи написать хороший классификатор и правильно его настроить, просто тестовый код.
Результаты в секундах, в скобочках отношение к С++ коду:
c++ g++ d dmd d gdc d ldc2 rust rustc
1 0.577 1.797 (3.11) 0.999 (1.73) 0.583 (1.01) 0.546 (0.933)
2 0.628 2.272 (3.617) 1.217 (1.937) 0.898 (1.429) 0.52 (0.935)

Второй вариант алгоритма активней использует сборщик мусора (который я никак не настраивал). Лучший результат выдал, конечно же, ldc2 — в полтора раза медленей С++ при активной сборке мусора, что, в итоге, не так уж и плохо. И даже очень хорошо, если сравнивать полное время выполнения программы: 5.4 сек (с учётом правки тов. roman_kashitsyn 3.4 сек) для C++ против 2.9 сек для D на ldc2.

Естественно, для чистоты эксперимента, код я никак специально не оптимизировал и сделал максимально эквивалентным.
Код на D
import std.stdio;
import std.math;
import std.format;
import std.datetime;

//version=COLLECT_MEASURES;
//version=MERGE_CLASSES;

struct Measure
{
    float x=0, y=0;

    auto opBinary(string op)( auto ref const Measure m ) const
        if( op == "+" || op == "-" )
    { mixin( "return Measure( x " ~ op ~ " m.x, y " ~ op ~ " m.y );" ); }

    auto opBinary(string op)( float m ) const
        if( op == "*" || op == "/" )
    { mixin( "return Measure( x " ~ op ~ " m, y " ~ op ~ " m );" ); }
}

unittest
{
    auto a = Measure(1,3);
    auto b = Measure(4,5);
    auto add = a + b;
    assert( add.x == 5 && add.y == 8 );
    auto dif = a - b;
    assert( dif.x == -3 && dif.y == -2 );
    auto mlt = a * 3;
    assert( mlt.x == 3 && mlt.y == 9 );
    auto div = b / 2;
    assert( div.x == 2 && div.y == 2.5 );
}

float sqr( float v ) { return v * v; }

float dist( ref const Measure a, ref const Measure b )
{ return sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) ); }

class Class
{
    Measure mean;
    size_t N;
    version(COLLECT_MEASURES)
        Measure[] measures;

    this( in Measure m )
    {
        mean = m;
        N = 1;
        version(COLLECT_MEASURES)
            measures ~= m;
    }

    void append( in Measure m )
    {
        mean = ( mean * N + m ) / ( N + 1 );
        N++;
        version(COLLECT_MEASURES)
            measures ~= m;
    }

    void merge( const Class m )
    {
        mean = ( mean * N + m.mean * m.N ) / ( N + m.N );
        N += m.N;
        version(COLLECT_MEASURES)
            measures ~= m.measures;
    }
}

unittest
{
    auto cls = new Class( Measure(1,2) );
    assert( cls.mean.x == 1 && cls.mean.y == 2 );
    assert( cls.N == 1 );
    cls.append( Measure(3,4) );
    assert( cls.mean.x == 2 && cls.mean.y == 3 );
    assert( cls.N == 2 );
}

class Classifier
{
public:
    Class[] list;
    float ncls_dist;

    this( float mdist ) { ncls_dist = mdist; }

    void classificate( ref const Measure m )
    {
        float min_dist = float.max;
        Class near_cls;

        foreach( i; list )
        {
            float d = dist( m, i.mean );
            if( d < min_dist )
            {
                min_dist = d;
                near_cls = i;
            }
        }

        if( min_dist < ncls_dist ) near_cls.append(m);
        else list ~= new Class(m);
    }

    void mergeClasses()
    {
        Class[] uniq;

        l: foreach( cls; list )
        {
            foreach( trg; uniq )
                if( dist( cls.mean, trg.mean ) < ncls_dist )
                {
                    trg.merge( cls );
                    continue l;
                }

            uniq ~= cls;
        }

        list = uniq;
    }
}

Measure[] readMeasuresFromFile( string name )
{
    auto file = File( name, "r" );
    Measure[] list;

    foreach( line; file.byLine() )
    {
        Measure tmp;
        formattedRead( line, "%f %f", &tmp.x, &tmp.y );
        list ~= tmp;
    }

    return list;
}

void main( string[] args )
{
    auto measures = readMeasuresFromFile( args[1] );

    StopWatch sw;

    sw.start();

    auto clsf = new Classifier(3);

    foreach( m; measures )
        clsf.classificate(m);

    version(MERGE_CLASSES)
        clsf.mergeClasses();

    sw.stop();

    writeln( "work time: ", sw.peek.nsecs / 1_000_000_000.0f );

    foreach( cls; clsf.list )
        writefln( "[%f, %f]: %d", cls.mean.x, cls.mean.y, cls.N );
}


Код на Rust
#![feature(duration)]
#![feature(duration_span)] 
#![feature(append)]
use std::ops::*;
use std::borrow::Borrow;
use std::f32;
use std::cell::RefCell;
use std::fs::File;
use std::io::BufReader;
use std::io::BufRead;
 
use std::time::Duration;
use std::env;
 
 
#[derive(Clone,Copy)]
struct Measure
{
    x : f32,
    y : f32
}
 
impl Measure{
#[allow(non_snake_case)]
    pub fn new(X:f32,Y:f32) -> Measure{
        Measure{
            x:X,
            y:Y
        }
    }
}
impl Add for  Measure{
    type Output = Measure;
    fn add(self, rhs:Measure) -> Measure {
        Measure{
            x: self.x + rhs.x,
            y: self.y + rhs.y,
        }
    }
}
 
impl Sub for Measure{
    type Output = Measure;
 
    fn sub(self, rhs: Measure) -> Measure {
        Measure{
            x: self.x - rhs.x,
            y: self.y - rhs.y
        }
    }
}
 
impl Div<f32> for Measure {
    type Output = Measure;
 
    fn div(self, rhs: f32) -> Measure {
        Measure{
            x: self.x / rhs,
            y: self.y / rhs
        }
    }
}
 
impl Mul<f32> for   Measure {
    type Output = Measure;
 
    fn mul(self, rhs: f32) -> Measure {
        Measure{
            x: self.x * rhs,
            y: self.y * rhs
        }
    }
}
 
#[inline]
fn sqr(v:f32)->f32
{
    v * v
}
 
fn dist (a: & Measure, b: & Measure) -> f32
{
    (sqr(a.x - b.x) + sqr(a.y - b.y)).sqrt()
}
#[derive(Clone)]
struct Class
{
    mean: Measure,
    count: usize,
#[cfg(collect_measures)]
    measures: Vec<Measure>
}
impl Class{
#[cfg(collect_measures)]
    pub fn new( m: Measure ) -> Class
    {
        Class{
            mean: m,
            count: 1,
            measures: vec![m.clone()]
        }
    }
#[cfg(not(collect_measures))]
    pub fn new( m: Measure ) -> Class
    {
        Class{
            mean: m,
            count: 1,
        }
 
    }
#[cfg(collect_measures)]
    pub fn append(&mut self, m: Measure){
       self.mean = ( self.mean * self.count as f32 + m ) /( self.count + 1)as f32;
       self.measures.push(m.clone());
       self.count += 1;
    }
#[cfg(not(collect_measures))]
    pub fn append(&mut self, m: Measure){
       self.mean = ( self.mean * self.count as f32 + m ) /( self.count + 1)as f32;
       self.count += 1;
    }
#[cfg(collect_measures)]
    pub fn merge(&mut self, m: &mut Class)
    {
        self.mean = ( self.mean * self.count as f32 + ((m.mean) * m.count as f32 )) / ( self.count  + m.count) as f32;
        self.count += m.count;
        self.measures.append(&mut m.measures);
    }
#[cfg(not(collect_measures))]
    pub fn merge(&mut self, m: &mut Class)
    {
        self.mean = ( self.mean * self.count as f32 + ((m.mean) * m.count as f32 )) / ( self.count  + m.count) as f32;
        self.count += m.count;
    }
 
}
#[test]
fn test_Measure()
{
    let a = Measure::new(1f32,3f32);
    let b = Measure::new(4f32,5f32);
    let add = a + b;
    assert!( add.x == 5f32 && add.y == 8f32 );
    let dif = a - b;
    assert!( dif.x == -3f32 && dif.y == -2f32 );
    let mlt = &a * 3f32;
    assert!( mlt.x == 3f32 && mlt.y == 9f32 );
    let div = &b / 2f32;
    assert!( div.x == 2f32 && div.y == 2.5f32 );
}
#[test]
fn test_Class()
{
    let mut cls = Class::new( Measure::new(1f32,2f32) );
    assert!( cls.mean.x == 1f32 && cls.mean.y == 2f32 );
    assert!( cls.count == 1 );
    cls.append( Measure::new(3f32,4f32) );
    assert!( cls.mean.x == 2f32 && cls.mean.y == 3f32 );
    assert!( cls.count == 2 );
}
 
struct Classifier
{
 
    list:Vec<RefCell<Class>>,
    ncls_dist:f32
}
 
impl Classifier{
    pub fn new(mdist:f32) -> Classifier{
        Classifier{
            list:Vec::new(),
            ncls_dist:mdist
        }
    }
    pub fn classificate(&mut self, m: Measure){
        let mut min_dist:f32 = f32::MAX;
        let mut near_cls = 0;
        let mut index:usize = 0;
        for i in self.list.iter()
        {
            let d = dist( &m, & i.borrow().mean);
            if d < min_dist
            {
                min_dist = d;
                near_cls = index;
            }
            index+=1;
        }
        if min_dist < self.ncls_dist{
             self.list[near_cls].borrow_mut().append(m);
        }
        else {
 
            self.list.push(RefCell::new( Class::new(m)));
        }
    }
#[allow(dead_code)]
    pub fn merge_classes(&mut self)
    {
        let mut uniq: Vec<RefCell<Class>>= Vec::new();
        for cls in self.list.iter(){
            let mut is_uniq = true;
            for trg in uniq.iter(){
                if dist( &cls.borrow().mean, &trg.borrow().mean) < self.ncls_dist
                {
                    trg.borrow_mut().merge(&mut *cls.borrow_mut());
                    is_uniq = false;
                    break;
                }
            }
            if is_uniq
            {
                uniq.push(RefCell::new(cls.borrow_mut().clone()));
            }
        }
        self.list = uniq;
    }
 
}
 
fn read_measures_from_file( name: String ) -> Vec<Measure> 
{
 
    let mut list:Vec<Measure>  = Vec::new();
    let f = File::open(name).unwrap();
    let mut reader = BufReader::new(&f);
    let mut ret_string = String::new();
    while  let Ok(size ) = reader.read_line( &mut ret_string){
        if size > 0
        {
            let len = ret_string.len() - 1;
            ret_string.truncate(len);
            let buffer:Vec<&str> = ret_string.split(' ').collect();
            let var:f32 = (buffer[0]).parse::<f32>().unwrap();
            let var2:f32 = (buffer[1]).parse::<f32>().unwrap();
            list.push(Measure::new(var,var2));
        }
        else{
             break;
        }
        ret_string.clear();
    }
    return list;
}
 
fn main()
{
    let measures = read_measures_from_file(env::args().skip(1).next().unwrap());
    let mut clsf =  Classifier::new(3f32);
    let d = Duration::span(||{
        for  i in measures{
            clsf. classificate(i);
        }
        if cfg!(merge_classes){
            clsf.merge_classes();
        }
    });
    println!("work time: {}", d.secs() as f64 + d.extra_nanos()as f64 / 1000000000.0f64);
    for i in clsf.list{
        let i = i.borrow();
        println!("[{}, {}]: {}",i.mean.x,i.mean.y, i.count);
    }
}


Код на С++
#include <vector>
#include <cmath>
#include <cfloat>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cassert>
#include <ctime>

using namespace std;

//#define COLLECT_MEASURES
//#define MERGE_CLASSES

class Measure
{
public:
    float x, y;

    Measure(): x(0), y(0) {}
    Measure( float X, float Y ): x(X), y(Y) {}
    Measure( const Measure& m ): x(m.x), y(m.y) {}

    Measure operator+( const Measure& m ) const
    { return Measure( x + m.x, y + m.y ); }

    Measure operator-( const Measure& m ) const
    { return Measure( x - m.x, y - m.y ); }

    Measure operator*( float v ) const
    { return Measure( x * v, y * v ); }

    Measure operator/( float v ) const
    { return Measure( x / v, y / v ); }
};

void test_Measure()
{
    Measure a(1,3);
    Measure b(4,5);
    auto add = a + b;
    assert( add.x == 5 && add.y == 8 );
    auto dif = a - b;
    assert( dif.x == -3 && dif.y == -2 );
    auto mlt = a * 3;
    assert( mlt.x == 3 && mlt.y == 9 );
    auto div = b / 2;
    assert( div.x == 2 && div.y == 2.5 );
}

inline float sqr( float v ) { return v * v; }

float dist( const Measure& a, const Measure& b )
{ return sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) ); }

class Class
{
public:
    Measure mean;
    size_t N;
    #ifdef COLLECT_MEASURES
    vector<Measure> measures;
    #endif

    Class( const Measure& m ): mean(m)
    {
        N = 1;
        #ifdef COLLECT_MEASURES
        measures.push_back(m);
        #endif
    }

    void append( const Measure& m )
    {
        mean = ( mean * N + m ) / ( N + 1 );
        N++;
        #ifdef COLLECT_MEASURES
        measures.push_back(m);
        #endif
    }

    void merge( const Class& m )
    {
        mean = ( mean * N + m.mean * m.N ) / ( N + m.N );
        N += m.N;
        #ifdef COLLECT_MEASURES
        measures.insert(measures.end(), m.measures.begin(), m.measures.end());
        #endif
    }
};

void test_Class()
{
    auto cls = Class( Measure(1,2) );
    assert( cls.mean.x == 1 && cls.mean.y == 2 );
    assert( cls.N == 1 );
    cls.append( Measure(3,4) );
    assert( cls.mean.x == 2 && cls.mean.y == 3 );
    assert( cls.N == 2 );
}

class Classifier
{
public:
    vector<Class*> list;
    float ncls_dist;

    Classifier( float mdist ): ncls_dist(mdist) {}

    void classificate( const Measure& m )
    {
        float min_dist = FLT_MAX;
        Class* near_cls;

        for( auto i = list.begin(); i != list.end(); ++i )
        {
            float d = dist( m, (*i)->mean );
            if( d < min_dist )
            {
                min_dist = d;
                near_cls = *i;
            }
        }

        if( min_dist < ncls_dist ) near_cls->append(m);
        else list.push_back( new Class(m) );
    }

    void mergeClasses()
    {
        vector<Class*> uniq;

        l: for( auto cls = list.begin(); cls != list.end(); ++cls )
        {
            bool is_uniq = true;
            for( auto trg = uniq.begin(); trg != uniq.end(); ++trg )
            {
                if( dist( (*cls)->mean, (*trg)->mean ) < ncls_dist )
                {
                    (*trg)->merge( **cls );
                    delete (*cls);
                    is_uniq = false;
                }
                if( !is_uniq ) break;
            }

            if( is_uniq ) uniq.push_back( *cls );
        }

        list = uniq;
    }

    ~Classifier()
    {
        for( auto i = list.begin(); i != list.end(); ++i )
            delete *i;
    }
};

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;
}

void runTests()
{
    test_Measure();
    test_Class();
}

int main( int argc, char* args[] )
{
    //runTests();

    auto measures = readMeasuresFromFile( args[1] );

    clock_t start = clock();

    auto clsf = new Classifier(3);

    for( auto i = measures.begin(); i != measures.end(); ++i )
        clsf->classificate( *i );

    #ifdef MERGE_CLASSES
    clsf->mergeClasses();
    #endif

    clock_t end = clock();

    cout << "work time: " << double(end - start) / CLOCKS_PER_SEC << endl;

    for( auto i = clsf->list.begin(); i != clsf->list.end(); ++i )
        cout << "[" << (*i)->mean.x << ", " << (*i)->mean.y << "]: " << (*i)->N << endl;

    delete clsf;
}


Код генератора выборки
import std.stdio;
import std.string;
import std.exception;
import std.random;
import std.math;

double normal( double mu=0.0, double sigma=1.0 )
{
    static bool deviate = false;
    static float stored;

    if( !deviate )
    {
        double max = cast(double)(ulong.max - 1);
        double dist = sqrt( -2.0 * log( uniform( 0, max ) / max ) );
        double angle = 2.0 * PI * ( uniform( 0, max ) / max );

        stored = dist * cos( angle );
        deviate = true;

        return dist * sin( angle ) * sigma + mu;
    }
    else
    {
        deviate = false;
        return stored * sigma + mu;
    }
}

struct vec { float x, y; }

vec randomVec( in vec m, in vec s ) { return vec( normal(m.x, s.x), normal(m.y, s.y) ); }

auto generate( size_t[vec] classes )
{
    vec[] ret;
    foreach( pnt, count; classes )
    {
        auto tmp = new vec[]( count );
        foreach( i, ref t; tmp )
            t = randomVec( pnt, vec(1,1) );
        ret ~= tmp;
    }
    return ret;
}

import std.getopt;

void main( string[] args )
{
    uint k;

    getopt( args, 
            "count-multiplier|c", &k
          );

    enforce( args.length == 2, format( "wrong number of arguments: use %s <output_file>", args[0] ) );

    auto f = File( args[1], "w" );
    scope(exit) f.close();

    auto vs = generate( [ vec(-8,8): 20 * k, vec(4,0) : 10 * k, vec(-6,-8) : 15 * k ] );

    foreach( v; vs.randomSample(vs.length) )
        f.writeln( v.x, " ", v.y );
}


Сборка
Тест 1
g++ -O2 -std=c++11 cls.cpp -o cls_cpp && echo "c++ g++ builded"
dmd -O -release cls.d -ofcls_d_dmd && echo "d dmd builded"
ldc2 -O2 -release cls.d -ofcls_d_ldc2 && echo "d ldc2 builded"
gdc -O2 cls.d -o cls_d_gdc && echo "d gdc builded"
rustc -O cls.rs -o cls_rs && echo "rust rustc builded"

Тест 2
g++ -O2 -D COLLECT_MEASURES -D MERGE_CLASSES -std=c++11 cls.cpp -o cls_cpp && echo "c++ g++ builded"
dmd -O -version=COLLECT_MEASURES -version=MERGE_CLASSES -release cls.d -ofcls_d_dmd && echo "d dmd builded"
ldc2 -O2 -d-version COLLECT_MEASURES -d-version MERGE_CLASSES -release cls.d -ofcls_d_ldc2 && echo "d ldc2 builded"
gdc -O2 -fversion=COLLECT_MEASURES -fversion=MERGE_CLASSES cls.d -o cls_d_gdc && echo "d gdc builded"
rustc -O --cfg collect_measures --cfg merge_classes cls.rs -o cls_rs && echo "rust rustc builded"


Версии компиляторов
g++ (GCC) 5.1.1 20150612 (Red Hat 5.1.1-3)
DMD64 D Compiler v2.067.1
GNU gdb (GDB) Fedora 7.9.1-13.fc22
LDC — the LLVM D compiler (0.15.2-beta1)
rustc 1.3.0-nightly (cb7d06215 2015-06-26)


PS. В языках Rust и Go не силён, если кто-нибудь захочет написать эквивалентный код (для полноты эксперимента) буду рад вставить результаты сюда.

UPD: спасибо тов. I_AM_FAKE за код на Rust

Комментарии (33)


  1. roman_kashitsyn
    26.06.2015 13:55
    +1

    Решая задачки на 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;
    }
    


    Так можно избежать большого количества копий строк.


    1. deviator Автор
      26.06.2015 14:12
      +1

      Согласен, мой косяк.


    1. FoxCanFly
      26.06.2015 14:47
      +4

      Просто ifstream — не лучшее решение, если нужна максимальная скорость работы с вводом/выводом.


      1. roman_kashitsyn
        26.06.2015 15:31

        > Просто ifstream — не лучшее решение, если нужна максимальная скорость работы с вводом/выводом

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

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

        std.stdio в D мне нравится одновременно простотой и эффективностью. Не нужно думать, где сколько букв l нужно писать в строке формата, компилятор сам может вставить правильный код. Ну и он бросает исключения в случае ошибок, не нужно смотреть коды возврата / флажки.


        1. 0xd34df00d
          27.06.2015 15:27

          Когда мне надо было прочитать файл с корреляционной таблицой на 3.5, кажется, гигабайта из кучи строк формата
          ENTITY_1 ENTITY_2 <integer>
          то cstdio (fscanf, в частности) был медленнее процентов на 10-15, чем ifstream — в конце концов, на каждой строке файла надо форматную строку "%s %s %f" ещё распарсить, в то время как на C++ знание о формате заложено в структуру и последовательность вызовов operator>>.

          Судя по профайлеру, в ifstream жралось феерически много времени на какую-то возню с локалями, избавиться от которой мне так и не удалось.

          В итоге открывал файл через mmap и писал самопальный токенайзер с парсером чисел (благо, не надо обрабатывать отрицательные числа, и т. п.). В итоге на непосредственно чтение файла стало тратиться совсем мало времени, большинство из которого было внутри memchr, и выигрыш в скорости был где-то процентов 35 — с 90 секунд до 50 время чтения упало.


      1. deviator Автор
        26.06.2015 15:33
        +1

        Возможно, а что сейчас принято использовать на С++ для ввода?


        1. FoxCanFly
          26.06.2015 16:17

          Большинству хватает fstream — редко когда нужна максимальная скорость ввода вывода файлов. Кому нужна — есть много альтернативных библиотек, вроде даже тот же QFile быстрее. Ну и пишут свои велосипеды с системными read()/write()


        1. BalinTomsk
          26.06.2015 18:05
          +1

          file mapping


  1. ik62
    26.06.2015 18:45

    Не сталкивались ли с какими-либо косяками при использовании не-dmd компилятора?


    1. deviator Автор
      26.06.2015 19:10

      Единственный косяк, который мне приходилось отлавливать не косяк по сути. Версия dmd всегда свежее версий frontend'ов gdc и ldc2. Но dmd я пользуюсь как основным, так что не могу полностью гарантировать, что их нет.


  1. artemonster
    26.06.2015 19:41

    builded


  1. biziwalker
    26.06.2015 21:16

    deviator а не могли бы вы предоставить сгенерированную выборку? К сожалению, нет возможности сгенерировать выборку с помощью вашего генератора на D. Но есть интерес в реализации алгоритма на Rust.

    PS: думаю Rust будет немного медленее, чем C++ из-за безопасности кода


    1. deviator Автор
      27.06.2015 03:47

      Было бы очень классно. Выборку я думаю всю предоставлять не имеет смысла, во-первых из-за того, что она 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


      1. withkittens
        27.06.2015 14:33

        Выложите, может быть, всё-таки ваш набор, для честности эксперимента? :)
        Или, по крайней мере, скажите, с каким --count-multiplier вызывался генератор выборки.
        А я тоже попробую написать версию на Rust.


        1. withkittens
          27.06.2015 16:07
          +1

          Ладно, методом тыка обнаружилось, что --count-multiplier ? 100k. :)


          1. deviator Автор
            27.06.2015 16:24

            да, ровно 100000


            1. withkittens
              27.06.2015 19:25

              С настройками как у вас, у меня получается ?54 класса с кол-вом точек от 1 до 342k в каждом из классов. Так и должно быть?


              1. withkittens
                27.06.2015 20:07

                Добавил слияние классов:

                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


                1. deviator Автор
                  27.06.2015 21:48

                  тов I_AM_FAKE напсал намного раньше чем Вы, просто я смог выложить это только сейчас. И у Вас нет сохранения набора точек в классах.


                  1. withkittens
                    27.06.2015 22:38

                    Да мне не жалко.

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

                    Потестировал код на 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++ оказалась медленнее (и это без слияния!). Хотя я уверен, что можно ускориться.


              1. deviator Автор
                27.06.2015 21:46

                да, так и должно быть


      1. biziwalker
        27.06.2015 21:30
        +1

        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
        


        1. biziwalker
          27.06.2015 21:50

          Получается Rust оказался почти в 3 раза быстрее C++ — что-то здесь не чисто! Код на C++ приводил к индентичному на Rust, единственное это я не реализовал ту фичу заложенную автором, которая включается с помощью #define COLLECT_MEASURES. А так на равных условиях, с отключенными фичами, Rust оказался быстрее. И всетаки надо сравнивать на одинаковом железе и с нормальными выборками. Предлагаю автору ( deviator ) этим заняться и сделать свои выводы кто кого быстрее в этой гонке.


          1. deviator Автор
            27.06.2015 21:56
            +1

            на большой выборке Rust всё равно победил)


    1. mx2000
      28.06.2015 00:32
      +1

      «безопасность» кода в Rust проверяется на стадии компиляции, что никак не отражается на эффективности конечного бинарника.


      1. deviator Автор
        28.06.2015 00:41

        Всего не знаю, но, мне кажется, что на C++ вообще нет такой безопасности.


      1. biziwalker
        28.06.2015 09:13

        Сталкивался на простых тестах сортировки с тем, что в Rust есть инструкции проверки на доступность элемента в массиве. Скорость просела в 1.5 раза по сравнению с C на сортировке вставками. Но благо Rust позволяет писать unsafe код, если хочется выжить максимум :)


  1. NCrashed
    27.06.2015 23:04
    +4

    Решил поиграться с 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_Cla


  1. mt_
    28.06.2015 14:09

    С моей точки зрения, заголовок некорректен.
    В данном конкретном случае нужно говорить не о сравнении языков, а о сравнении скорости функций ввода-вывода двух конкретных реализаций библиотек. Это по большей части.
    Являясь профессионалом в D, вы подготовили сравнительно оптимальный код D и «просто работающий» код С++. После чего получили те результаты, которые получили. Что они действительно показывают — вопрос отдельный. Но уж точно не «сравнение производительности двух языков».


    1. withkittens
      28.06.2015 14:56

      а о сравнении скорости функций ввода-вывода двух конкретных реализаций библиотек
      Таблица в статье не включает ввод-вывод.


      1. mt_
        28.06.2015 17:06

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


  1. kraidiky
    28.06.2015 15:20
    +7

    Как-то раз в бородатом детстве в 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) Оптимизатор в фортране написан сошедшими на землю богами.


    1. biziwalker
      28.06.2015 15:48

      Особенно верно, если учесть, что у большинства современных языков на бэкенде LLVM или GCC