Pull to refresh

Сравнение производительности языков на примере простейшего классификатора

Reading time 10 min
Views 33K
Доброго времени суток, хабр!


Моим основным ЯП является 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
Tags:
Hubs:
+17
Comments 34
Comments Comments 34

Articles