LINUX.ORG.RU

100 dynamic_cast'ов за 1 миллисекунду

 ,


0

3
#include <iostream>
#include <typeinfo>
#include <sys/time.h>
#include <stdint.h>

using namespace std;


// Type Lists
template< typename T, T v = T() >
struct Value
{
    enum { val = v };
    typedef T value_type;
};

struct NullItem
{
    static void Print() { std::cout << std::endl; }
};

template< typename V, typename L >
struct List
{
    typedef V value_type;

    static void Print()
    {
        std::cout << value_type::val << ", ";
        L::Print();
    }
};

template< class List > struct Next;

template< class V, class L >
struct Next< List< V, L > >
{
    typedef L NextType;
};

template< unsigned n, int i = 0, int until = n + i, class G = NullItem >
class Generate
{
    typedef List< Value< int, i >, G > NewList;
public:
    typedef typename Generate< n, i + 1, until, NewList >::NextType NextType;
};

template< unsigned n, int until, class G >
class Generate<n, until, until, G>
{
public:
    typedef G NextType;
};


// Linear class hierarchy
struct IBase
{
    virtual ~IBase() {}
    virtual void Print() = 0;
};

template< class TList >
struct CRTP : CRTP< typename Next< TList >::NextType >
{
    virtual void Print()
    {
        cout << typeid( *this ).name() << " " << TList::value_type::val << endl;
    }
};

template<>
struct CRTP< NullItem > : IBase
{
    // IBase
    virtual void Print()
    {
        cout << typeid( *this ).name() << endl;
    }
};


void TestDownCast( IBase *b )
{
    static const int NUM_CASTS = 10 * 1000;

    struct timeval tvStart, tvEnd;
    gettimeofday( &tvStart, NULL );

    for( int i = 0; i < NUM_CASTS; ++i )
    {
        CRTP< NullItem > *pCRTP = dynamic_cast< CRTP< NullItem > * >( b );
        /*if ( pCRTP )
        {
            cout << "downcasted successfully" << endl;
        }*/
    }

    gettimeofday( &tvEnd, NULL );
    int64_t elapsed = (int64_t)( tvEnd.tv_sec - tvStart.tv_sec ) * 1000000 +
                               ( tvEnd.tv_usec - tvStart.tv_usec );

    cout << NUM_CASTS << " casts : elapsed " << elapsed << " us" << endl;
}


int main()
{
    static const int NUM_ITEMS = 500;
    typedef Generate< NUM_ITEMS >::NextType GenList;
    //GenList::Print();

    CRTP< GenList > r;
    //r.Print();

    TestDownCast( &r );

    return 0;
}
g++ dc.cpp -o dc
./dc
10000 casts : elapsed 97958 us

Не «ШОК!ФОТО!» ли это?

dynamic_cast

А что ты хотел?

Не «ШОК!ФОТО!» ли это?

Добавь тег «я познаю мир»

no-such-file ★★★★★ ()

Динамик каст тормоз, если собственно сам каст не нужен, но надо быстро проверить тип, typeid() бодрее.

yoghurt ★★★★★ ()

И у нас есть суперхаккиллер1997 от Си++!

tailgunner ★★★★★ ()
Ответ на: комментарий от yoghurt

надо быстро проверить тип

Вообще, во всех азбуках пишут, что проверять тип - зло (а dynamic_cast - адская сотона), что так верстают пишут только мудаки. И я с ними согласен - если вы не используете полиморфизм, нафиг вам вообще ООП?

no-such-file ★★★★★ ()
Ответ на: комментарий от no-such-file

нафиг вам вообще ООП?

Очень часто того огрызка, который в плюсах по недоразумению называют ООПом, просто не хватает, а очень хочется.

anonymous ()
Ответ на: комментарий от anonymous

просто не хватает, а очень хочется.

Если тебе хочется знать конкретный тип объекта, то это какбэ не совсем ООП.

no-such-file ★★★★★ ()

у меня 68 808 511 наносекунд на 10000 получается итого по 6880 наносекунды на каждый.

anonymous ()

12 студия в венде вообще отказалась этот код компилячить. Падает.

anonymous ()
    for( int i = 0; i < NUM_CASTS; ++i )
    {
        CRTP< NullItem > *pCRTP = dynamic_cast< CRTP< NullItem > * >( b );
        /*if ( pCRTP )
        {
            cout << "downcasted successfully" << endl;
        }*/
    }

Ты посмотри ассемблер, может оно выкинуло этот код.

DELIRIUM ★★★★★ ()
Ответ на: комментарий от anonymous

Ну круто, у тебя проц быстрее моего в 1.5 раза.
cast за ~7 микросекунд это как, это нормально? Или может пора уже на java переходить всем плюсовикам?

nerdogeek ()
Ответ на: комментарий от DELIRIUM

Там надо либо -O0, либо вынести CRTP< NullItem > *pCRTP за функцию как volatile — получается медленно, да.

quasimoto ★★★★ ()
Ответ на: комментарий от anonymous

Поставь NUM_ITEMS поменьше, а цикл NUM_CASTS побольше

static const int NUM_ITEMS = 50;

nerdogeek ()
Ответ на: комментарий от nerdogeek

хз. У меня Intel® Core™ i5-650 Processor (4M Cache, 3.20 GHz)

Кстати собранное шлангом выдает уже 45 378 188 наносекунд

anonymous ()
Ответ на: комментарий от anonymous

хм. вообще оно выдает от 45 378 188 до 51 648 671 .... Но у меня тут музыка играется, и виртуалка :))

anonymous ()
Ответ на: комментарий от no-such-file

во всех азбуках пишут, что проверять тип - зло

Это верно

если вы не используете полиморфизм, нафиг вам вообще ООП?

Бывает, что иначе никак (либо всё переписывать, либо касты-тайпиды - самый простой путь в рамках сложившейся ситуации).

yoghurt ★★★★★ ()

И что даёт измерение дин. кастов? Имхо, это капля в море из всего кода типичных приложений, глупо мерить таким тестом железо или что-то ещё.

menangen ★★★★★ ()
Ответ на: комментарий от nerdogeek

эммм ... поставил NUM_ITEMS = 50; цикл на 100000, собрал студией, выплюнула все за 700 микросекунд.

anonymous ()
Ответ на: комментарий от nerdogeek

Есть workaround dynamic_cast'у

Такой downcast?

  // uses RTTI in dbg and fastbuild. asserts are disabled in opt builds.
  assert(f == NULL || dynamic_cast<To>(f) != NULL);
  return static_cast<To>(f);

если так нужно, то RTTI для бедных в иерархии классов с виртуальными методами можно устроить вызовом виртуального TypeId Base::whoIAm() const; и последующим static_cast.

RTTI для такого полезен

            Holder<T> * holder = dynamic_cast<Holder<T>*>(iholder.get());
            return holder->instance_;

яснопонятно :) Хотя бы на 0 проверили, а то с тем же успехом можно было делать static_cast.

quasimoto ★★★★ ()
Ответ на: комментарий от no-such-file

Если тебе хочется знать конкретный тип объекта, то это какбэ не совсем ООП.

Угу, угу. Но есть существующие библиотеки, которые не позволяют работать по другому. Например, Qt.

anonymous ()
Ответ на: комментарий от yoghurt

либо всё переписывать, либо касты-тайпиды - самый простой путь в рамках сложившейся ситуации

Бывает конечно, т.к. жизнь трудна и мир жесток. Но зачем запиливать это изначально, by design, мне не понятно.

no-such-file ★★★★★ ()
Ответ на: комментарий от anonymous

Например, Qt.

В кутях вывернулись на изнанку через задницу, лишь бы не использовать dynamic_cast. Там своя кастилка, а все типы имеют свой, кутешный typeId или что-то вроде этого. Я уж не говорю про их метаобъекты.

no-such-file ★★★★★ ()

Неправда, в типовом случае на GCC/Linux dynamic_cast занимает около 10-15 тактов.

quiet_readonly ★★★★ ()

dynamic_cast в таком виде, как он есть в с++, нужен только для того, чтобы можно было писать так:

struct A { virtual ~A(); }; struct B { virtual ~B(); };
struct C : A, B {};
int main() {
    A* a = new A;
    B* b = dynamic_cast<B*>(a);
    assert((void*)a != (void*)b);
}
В остальных случаях он может и должен быть заменен виртуальными функциями вместе со static_cast.

vzzo ★★★ ()
Ответ на: комментарий от nerdogeek

Вот ещё велосипед:

#include <cstddef>
#include <cstdint>

template <size_t word_size, size_t tag_size, typename T>
class TaggedPtr {

    uintmax_t addr;

    static constexpr uintmax_t one = 1;
    static constexpr uintmax_t end(size_t i) { return one << (word_size - 1 - i); }
    static constexpr uintmax_t begin(size_t i) { return one << i; }

#define FOR_TAG_BIT(I) for (size_t I = 0; I < tag_size; ++I)

public:

    TaggedPtr(T *p, uintmax_t tag) : addr(reinterpret_cast<uintmax_t>(p)) {
        FOR_TAG_BIT(i) tag & begin(i) ? addr |= end(i) : addr &= ~end(i);
    }

    T* operator&() {
        uintmax_t p = addr;
        FOR_TAG_BIT(i) p &= ~end(i);
        return reinterpret_cast<T*>(p);
    }

    uintmax_t tag() {
        uintmax_t tag = 0;
        FOR_TAG_BIT(i) if (addr & end(i)) tag |= begin(i);
        return tag;
    }

#undef FOR_TAG_BIT

};

template <typename Top, typename Sub>
struct TypeRelId;

template <typename T>
using Ptr = TaggedPtr<64, 4, T>;

template <typename Top, typename Sub>
Ptr<Top> upcast(Sub *b) {
    return Ptr<Top>(b, TypeRelId<Top, Sub>::value);
}

template <typename Sub, typename Top>
Sub* downcast(Ptr<Top> a) {
    return a.tag() == TypeRelId<Top, Sub>::value ? static_cast<Sub*>(&a) : 0;
}

//

#include <cstdio>

struct A {
    virtual ~A() {}
    virtual void test() const = 0;
};

struct B : public A {
    virtual void test() const { puts("B"); }
};

template <>
struct TypeRelId<A, B> { enum { value = 0 }; };

int main() {
    auto a = upcast<A>(new B);
    (&a)->test();
    auto b = downcast<B>(a);
    if (b) b->test();
}
quasimoto ★★★★ ()
Ответ на: комментарий от no-such-file

ООП интерфейсы и алгебраические типы это две стороны одной медали (expression problem) — в Scala у нас может быть abstract class / trait IFace и куча case class-ов которые делают ему extends — хотим, можем поднять в IFace и работать ООП-шным полиморфизмом, или можем разобрать объект IFace в паттерн-матчинге по конкретным case class-ам и работать уже имея информацию о конкретном типе объекта. Как-то там с этим нет проблем (плюс там есть sealed иерархии, так что компилятор может проверять «герметичность» паттерн-матчинга, типа как со switch по enum в C++).

http://www.artima.com/pins1ed/case-classes-and-pattern-matching.html

http://en.wikipedia.org/wiki/Expression_problem

quasimoto ★★★★ ()
Последнее исправление: quasimoto (всего исправлений: 1)
Ответ на: комментарий от quasimoto

Как-то там с этим нет проблем

А что этот pattern matching бесплатный что ли? Или работает гораздо быстрее чем dynamic_cast?

kamre ★★★ ()

Упарываться тоже нужно в меру. У тебя вроде получается класс в NUM_ITEMS наследований через которые пытаешься делать каст и рантайм делает это за O(NUM_ITEMS).

mashina ★★★★★ ()
Ответ на: комментарий от quasimoto
template <size_t word_size, size_t tag_size, typename T>
class TaggedPtr {
    struct Word { uintmax_t tag : tag_size, ptr : word_size - tag_size; };
    Word addr;
public:
    TaggedPtr(T *p, uintmax_t tag) { addr.ptr = reinterpret_cast<uintmax_t>(p); addr.tag = tag; }
    T* operator&() { return reinterpret_cast<T*>(addr.ptr); }
    uintmax_t tag() { return addr.tag; }
};
quasimoto ★★★★ ()

профайлером гонял?

anonymous ()
Ответ на: комментарий от yoghurt

Почему он тормоз если по идее нужно просто сравнить парочку указателей? В бенчмарке что-то не так, хотя хз

vertexua ★★★☆☆ ()
Последнее исправление: vertexua (всего исправлений: 2)
Ответ на: комментарий от vertexua

Сравнить пару указателей на что, простите? :)

yoghurt ★★★★★ ()
Ответ на: комментарий от kamre

А что этот pattern matching бесплатный что ли? Или работает гораздо быстрее чем dynamic_cast?

http://stackoverflow.com/q/754166

http://stackoverflow.com/q/12218641

http://stackoverflow.com/q/9027384

http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf

Т.е. это немного разные вещи — PM это простой механизм, в отличии от.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Как-то там с этим нет проблем

Дык и с dynamic_cast нет проблем. Кроме той, что это тормоза.

в Scala у нас может быть

Может. Но тормозит оно, я думаю покрепче, чем кресты даже с dynamic_cast.

no-such-file ★★★★★ ()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от no-such-file

Дык и с dynamic_cast нет проблем. Кроме той, что это тормоза.

С ним на самом деле тоже нет проблем. В плюсах есть проблема с людьми, которые гогнокодят на шаблонах всё подряд.

mashina ★★★★★ ()
Ответ на: комментарий от no-such-file

Дык и с dynamic_cast нет проблем.

Оно не O(n) от глубины наследования? (type)case по типам/значениям -то по идее должен и просто O(1) быть и фактически быстрым.

Но тормозит оно, я думаю покрепче, чем кресты даже с dynamic_cast.

http://www.open-std.org/jtc1/sc22/wg21/docs/TR18015.pdf

http://lampwww.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf

Как-то совсем в разных тонах описывается. Их просто не нужно сравнивать, я думаю — одно это глубокий downcast, другой — кто это + useAsInstanceOf.

quasimoto ★★★★ ()
Ответ на: комментарий от quasimoto

Всё ништяк, но нужно по-хорошему (n^2)/2 таких объяв TypeRelId создавать для описания иерархии наследования глубиной n.

nerdogeek ()
Ответ на: комментарий от nerdogeek

А какая вообще магия там должна быть, что зависимость линейная от NUM_ITEMS? Результат от Print на GenList* -(implicit upcast)-> IBase* -(dynamic_cast)-> CRTP<NullItem>* в итоге (NUM_ITEMS - 1).

Если сделать

template <> struct TypeRelId<IBase, GenList> { enum { value = 0 }; };
template <> struct TypeRelId<IBase, CRTP<NullItem>> { enum { value = 0 }; };

т.е. static_cast с проверкой, то результат тот же, линейной зависимости больше нет — константно, быстрее в over дофига раз (~10^6?).

quasimoto ★★★★ ()
Последнее исправление: quasimoto (всего исправлений: 1)
Ответ на: комментарий от anonymous

Очень часто того огрызка, который в плюсах по недоразумению называют ООПом, просто не хватает, а очень хочется.

Лол, маргинальщику БОМБАНУЛО.

anonymous ()
Ответ на: комментарий от quasimoto

Нет, ну это понятно. Если есть такая последовательность наследования: IBase <- A <- B <- C <- D <- ... <- Z1050; то нужно знать что не только IBase кастуется во все дочерние элементы (т.е. N случаев cast), но и дочерние классы аналогично (A во все дочерние N-1; B во все дочерние N-2). Т.е. последовательность N + (N-1) + (N-2) +...+ 1 ~= (N^2)/2 - число объявлений template <> struct TypeRelId<X, Y>. Т.е. получается что при константном времени реализация требует квадрат объявлений struct TypeRelId<> и log2(N^2) бит на хранение тегов

Да и в 4 бита тега не так много информации получится хранить

nerdogeek ()
Ответ на: комментарий от yoghurt

Сравнить пару указателей на что, простите? :)

На vtbl, конечно же.

k_andy ★★★ ()
Ответ на: комментарий от nerdogeek

Это тоже понятно, но 1) эти все отношения могут быть не нужны в использовании, 2) их бы не нам, а компилятору писать, 3) всё равно не заменят dynamic_cast-а который может оперировать информацией неизвестной во время компиляции.

http://www.stroustrup.com/fast_dynamic_casting.pdf

Да и в 4 бита тега не так много информации получится хранить

Ну на x86_64 можно 16 взять. Но это я так — можно просто взять слово.

quasimoto ★★★★ ()
Ответ на: комментарий от yoghurt

dynamic_cast по иерархии классов шерстит.

Ну так иерархия известна в compile-time, то есть проверка сводится к сравнению с конечным набором значений.

k_andy ★★★ ()

Топик не читал.

Измерение без опции компилятора -O2 или -O3 вообще ни о чём.

anonymous ()
Ответ на: комментарий от k_andy

Ну так иерархия известна в compile-time

Не особенно, если указатель на объект лежит, например, в векторе. Вектор не языковая конструкция и что там у него внутри происходит компилятор знать не может.

Допустим у нас vector<A*>, откуда компилятору знать, что некоторые элементы на самом деле B* ?

no-such-file ★★★★★ ()
Ответ на: комментарий от k_andy

С чего вдруг она известна? А ещё не забывай про каст «братьев», который в статике в точке компиляции вообще могут быть никак не связаны. Скажем, есть A и B, два отдельных самостоятельных класса, не связанных общей иерархией. Ты делаешь в какой-то функции dynamic_cast A к B. И что, по-твоему должен делать компилятор?

anonymous ()
Ответ на: комментарий от nerdogeek

Или может пора уже на java переходить всем плюсовикам?

Переходи. Ты уже пишешь на C++ как на Java.

rupert ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.