Всем привет!

Начало тут: http://www.rsdn.ru/Forum/Message.aspx?mid=2385218

Автор: SergH
Дата: 27.02.07

Продолжение — да, есть результаты, местами даже положительные

Тест:

(define func (lambda (x)    
    (if (= x 0)           
        1          
        (* x (func (- x 1)))    
    )
))

(map func 1000 1000 1000)

32-х разрядная Windows XP, 2 процессора Intel EM64 (данные примерные, по памяти):

* стандартный аллокатор, 0 потоков — 16.6 секунд
* стандартный аллокатор, 3 потока — 10.8 секунд
* быстрый аллокатор, 0 потоков — 4.2 секунды
* быстрый аллокатор, 3 потока — 3.5 секунд

Windows XP, Intel Core 2 Duo:

* стандартный аллокатор, 0 потоков — 8.9 секунд
* стандартный аллокатор, 2 потока — 9.5 секунд
* стандартный аллокатор, 3 потока — 9.6 секунд
* быстрый аллокатор, 0 потоков — 3 секунды
* быстрый аллокатор, 2 потока — 2.3 секунды
* быстрый аллокатор, 3 потока — 2.3 секунды

Mac OS X, Intel Core 2 Duo (вот чОртова операционная система! на 1000 программа падает, проверяли на 700, кроме того,
с быстрым алокатором тоже падает. И всю положительную статистику портит... Не зря их символ — надкусанное яблоко):

* стандартный аллокатор, 0 потоков — 3.827 секунд
* стандартный аллокатор, 3 потока — 9.272 секунд


Debian Linux (наверное, 64 разряда) 2 процессора Intel EM64:


* Лог для стандартного аллокатора:

/home/users/sergh/code/bin$ time ./executer out.sch
(inf inf inf)
time: 12746 milliseconds
real    0m12.750s
user    0m12.645s
sys    0m0.096s
/home/users/sergh/code/bin$ time ./executer out.sch 1
(inf inf inf)
time: 12460 milliseconds
real    0m12.464s
user    0m17.893s
sys    0m1.944s
/home/users/sergh/code/bin$ time ./executer out.sch 2
(inf inf inf)
time: 13268 milliseconds
real    0m13.271s
user    0m28.370s
sys    0m5.916s
/home/users/sergh/code/bin$ time ./executer out.sch 3
(inf inf inf)
time: 15178 milliseconds
real    0m15.182s
user    0m41.039s
sys    0m16.873s
/home/users/sergh/code/bin$ time ./executer out.sch
(inf inf inf)
time: 12603 milliseconds
real    0m12.605s
user    0m12.569s
sys    0m0.004s
/home/users/sergh/code/bin$ time ./executer out.sch 1
(inf inf inf)
time: 12686 milliseconds
real    0m12.689s
user    0m17.657s
sys    0m2.704s
/home/users/sergh/code/bin$ time ./executer out.sch 1
(inf inf inf)
time: 12442 milliseconds
real    0m12.446s
user    0m18.081s
sys    0m1.692s

* Лог для быстрого аллокатора:

/home/users/sergh/code/bin$ time ./executerfa out.sch
(inf inf inf)
time: 10979 milliseconds
real    0m11.065s
user    0m10.477s
sys    0m0.588s
/home/users/sergh/code/bin$ time ./executerfa out.sch 1
(inf inf inf)
time: 10728 milliseconds
real    0m10.803s
user    0m14.485s
sys    0m2.488s
/home/users/sergh/code/bin$ time ./executerfa out.sch 2
(inf inf inf)
time: 12616 milliseconds
real    0m12.692s
user    0m26.938s
sys    0m8.437s
/home/users/sergh/code/bin$ time ./executerfa out.sch 3
(inf inf inf)
time: 12929 milliseconds
real    0m13.005s
user    0m32.134s
sys    0m16.817s
/home/users/sergh/code/bin$ time ./executerfa out.sch
(inf inf inf)
time: 10944 milliseconds
real    0m11.017s
user    0m10.373s
sys    0m0.644s
/home/users/sergh/code/bin$ time ./executerfa out.sch 1
(inf inf inf)
time: 10628 milliseconds
real    0m10.704s
user    0m14.389s
sys    0m2.584s
/home/users/sergh/code/bin$ time ./executerfa out.sch
(inf inf inf)
time: 10956 milliseconds
real    0m11.029s
user    0m10.505s
sys    0m0.524s
/home/users/sergh/code/bin$ time ./executerfa out.sch 1
(inf inf inf)
time: 10595 milliseconds
real    0m10.671s
user    0m14.709s
sys    0m2.188s
/home/users/sergh/code/bin$ time ./executerfa out.sch 2
(inf inf inf)
time: 12517 milliseconds
real    0m12.593s
user    0m26.430s
sys    0m8.765s

В общем, есть небольшой, но стабильный выигрыш при использовании 1-го дополнительного потока и быстрого аллокатора. Ещё,
обратите внимание на соотношение врёмён real/usr/sys — в случае использования двух или трёх дополнительный потоков,
sys очень вырастает, за счёт этого всё работает неэффективно. Правда, usr тоже вырастает, и не совсем понятно,
куда же оно уходит Но это и на остальных системах непонятно

Windows XP, Celeron 2Gz, 512Mb памяти. Это моя машинка Процессор один. Тем не менее, при использовании
быстрого аллокатора, примерно через три секунды оперативная память кончается и начинается свопинг. Task Manager
показывает, что загрузка процессора падает с 100% до 10%, а потом и до 2-3%. В этой ситуации многопоточная версия
работает быстрее даже на однопроцессорной машине — пока один поток ждёт окончания свопинга, второй может работать.
Эффект не очень большой, но заметный — примероно -20%. Правда, стандартный аллокатор не приводит к свопингу и
за счёт этого отрабатывает почти в два раза быстрее. И, конечно, без каких-либо преимуществ для многопоточной версии.

---

Более полный отчёт: http://sergh.pisem.net/diplom.html#2 — история + результаты

Там же исходники.

Здравствуйте, SergH, Вы писали:

>>..

Да, небольшое пояснение всё-таки нужно. Стандартный аллокатор это new + delete, быстрый аллокатор выглядит так:

#ifdef USE_FAST_ALLOCATOR

namespace allocator
{
    const int blockSize = 1024 * 1024 * 10;

    inline void* malloc(size_t count)
    {
#ifdef _WIN32
        // VC standard
        static __declspec(thread) char* begin = 0;
        static __declspec(thread) char* end = 0;
#else
        // GCC standard
        static __thread char* begin = 0;
        static __thread char* end = 0;
#endif 

        if ((count & 0x0f) != 0)
        {
            // 16-byte address alignment
            count &= ~0x0f;
            count += 0x010;
        }

        if (end - begin < (int)count)
        {
            // need allocate new block
            begin = (char*)::malloc(blockSize);
            end = begin + blockSize;
        }

        char* tmp = begin;
        begin += count;

        return tmp;
    }

    inline void free(const void* po)
    {
    }
}

inline void* operator new (size_t count) throw (std::bad_alloc)
{
    return allocator::malloc(count);
}

inline void operator delete (void* p) throw()
{
    allocator::free(p);
}

#endif

Как вариант — попробуй гарбадж-коллектер. Хотя бы на основе обыкновенного пула (ведь большинство создаваемых объектов имеют одинаковый размер — очень удобно). Это приведёт к некоторому замедлению (большой простор для оптимизации ), но значительно сократит объём выделяемой памяти.

Здравствуйте, frogkiller, Вы писали:

F>Как вариант — попробуй гарбадж-коллектер. Хотя бы на основе обыкновенного пула (ведь большинство создаваемых объектов имеют одинаковый размер — очень удобно). Это приведёт к некоторому замедлению (большой простор для оптимизации ), но значительно сократит объём выделяемой памяти.

Можетбытькогданибудь
На данный момент работа над проектом закончена/приостановлена.

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