Pull to refresh

Comments 55

берем кандидата (нечетного само собой), делим на все известные простые числа, меньшие чем половина кандидата.
А почему не корень кандидата?
UFO just landed and posted this here
Зачем вычислять его каждый раз? Достаточно один раз запомнить его в переменной. А квадратный корень очень просто и быстро вычисляется бинарным поиском за логарифмическое время.
UFO just landed and posted this here
Так и есть, выйгрышь значительный.
Знаца, 16 нитей, мой ноутбук:
умножаем (knownPrime*2<candidate): 58.101
делим (knownPrime<candidate/2): 107.577
корень (knownPrima<sqrt(candidate)): 0.825

на графиках использовалось умножение
UFO just landed and posted this here
пример кода можно? я на С только лабораторные в институте делал, боевых навыков не имею

а так, сам в шоке, думал где выход из цикла несанкционированный — нет, все честно
UFO just landed and posted this here
knownPrime<<1 < candidate: 47.925
knownPrime >1: 45.859
имелось в виду:
knowPrime меньше candidate сдвиг в право на 1: 45.859
UFO just landed and posted this here
В C# операции вроде *2, 4, 8… и деление на степени двойки оптимизированы.
В IL-коде еще будут операции умножения, а вот уже в ассемблерном после JIT будут только сдвиги. Однако в результирующем ASM для деления и умножения будет больше mov-ов.

C#
var j = i / 2;
IL:
L_0004: ldloc.0
L_0005: ldc.i4.2
L_0006: div
L_0007: stloc.1
ASM:
0000003f mov eax,dword ptr [rsp+20h]
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax

C#:
var k = i >> 1;
IL:
L_0008: ldloc.0
L_0009: ldc.i4.1
L_000a: shr
L_000b: stloc.2
ASM:
00000054 mov eax,dword ptr [rsp+20h]
00000058 sar eax,1
0000005a mov dword ptr [rsp+28h],eax
Судя по этому коду
00000043 cdq
00000044 sub eax,edx
00000046 sar eax,1

у вас переменная — со знаком, поэтому возникает этот дополнительный код если сравнивать просто со сдвигом.
Но вот этой вот магии мне всё равно не понять:
00000048 mov dword ptr [rsp+2Ch],eax
0000004c mov eax,dword ptr [rsp+2Ch]
00000050 mov dword ptr [rsp+24h],eax

Кагбэ temp = eax; eax = temp; result = eax;
Да, магия странная. Сейчас проверил на Int64 вместо Int32, т.к запускаю у себя под 64-битной ОС. Никуда эти странные mov-ы не исчезли. Можно еще на досуге посмотреть, как JIT от Mono себя ведет в подобной ситуации.

Int64 i = 10;
0000003a mov qword ptr [rsp+20h],0Ah

Int64 j = i / 2;
00000043 mov rax,qword ptr [rsp+20h]
00000048 cqo
0000004a sub rax,rdx
0000004d sar rax,1
00000050 mov qword ptr [rsp+38h],rax
00000055 mov rax,qword ptr [rsp+38h]
0000005a mov qword ptr [rsp+28h],rax

Int64 k = i >> 1;
0000005f mov rax,qword ptr [rsp+20h]
00000064 sar rax,1
00000067 mov qword ptr [rsp+30h],rax
Во-первых, если вычислять числа последовательно или почти последовательно (т.е. если количество чисел, обрабатываемых последовательно одним выч. узлом, сильно меньше, чем сами числа), то при переходе от n на n+m (где m сильно меньше n) корень легко пересчитывается: единичка либо прибавляется, либо нет :)

Во-вторых, в качестве альтернативы можно сравнивать p<=sqrt(n), а можно p*p<=n, и тут тоже можно придумать всякие оптимизации… ;)
Прошу прощения, неправильно написал. Должно быть «т.е. если разрывы между числами, обрабатываемыми одним выч. узлом, сильно меньше, чем сами числа».
с точки зрения правильности алгоритма — абсолютно верно, с точки зрения оценки вычислительных мощностей — не существенно
на самом деле, вспомнил о квадрате, после того, как результаты для первого графика получил, соответственно, пришлось оставить неоптимальный алгоритм поиска, чтобы сравнение было верно
Для больших чисел разница будет очень существенной.
Не думал, что мой ноутбук может серверную железяку переплюнуть.
Кто-то, Вы или я, неправильно понимает графики. ПО оси абсцисс — время, т.е. «меньше-лучше». Графики Opteron'а в обоих случаях выше других, т.е. при равном количестве нитей, оптерону требуется большее время. Где «переплюв»?
ноутбук на коре дуо. Оптерон серверная железка.
Виноват, не знал… В таком случае, видимо, это означает (временный) конец холивора AMD vs. Intel…
оптерон не n-ядерный похоже был. в параллельных вычислениях это играет свою роль.
2-x ядерный, это то и удивительно
UFO just landed and posted this here
если общественность интересует — выложу, выкладывать быдло код не хочется, а приводить его в порядок просто так — лень
я бы погладел.
За былость не боитесь.
ок. но в начале код в порядок все-таки приведу.
Вообще-то в таких исследованиях принято выкладывать исходный код, а то без него зачастую непонятно что к чему.
Выкладывайте обязательно.
UFO just landed and posted this here
Сейчас я укажу на недостатки к которым бы серьёзные дядечки придрались обязательно. (В универе пожурили бы и поставили хор., а вот

в исследовательском отделе коммерческой компании во все дырки бы…)

1. Непонятно что именно исследовалось.
В первом абзаце написано «нити»:
в зависимости от количества нитей.

Тогда как в вариантах уже «процессы»:
Берем кандидата на простое число, отдаем его процессу, который его считает.
Берем кандидата,

кормим бездельничающему процессу
Т.е. нити или процессы? (Накладные расходы на создание процесса)
Рекомендация: писать об этом явно и недвусмысленно, всегда показывать исходники тестов.

2. Непонятно что именно исследовалось. И, кажись, сам автор этого не понял.
2.1. Исследовалась ли качество реализации .Net framework в зависимости от архитектуры процессора?
2.2. Исследовалась ли скорость переключения в различных версиях .Net framework? (На висте минимальная версия 3.0, а на сервере какая

стояла?)
Рекомендация: исследовать на одной версии виртуальной машины. (Сначала 3.0, например, потом 3.5)

3. Непонятно что именно исследовалось. Автор этого сам не знает, и отсюда непонятные результаты.
Очень обескуражили результаты на AMD. Не думал, что мой ноутбук может серверную железяку переплюнуть. Может, есть тут

знатоки железа — поделитесь, в чем может быть дело?
А, по-моему, исследовалась как раз реализация механизма переключения

в различных ОС.
В висте и получилось быстрее.
Рекомендация: исследовать на одной версии ОС.
Т.е. всё кроме исследуемого параметра должно быть одинаковым.


Заключение:
Автор — молодец, рекомендую продолжать, но только более вдумчиво.
За развернутый комментарии спасибо.
исследовалось то, как кол-во нитей или процессов (т.к. нет устоявшегося перевода), которые Thread, влияют на скорость вычисления, если не изменять базовый алгоритм.
ВМ я указал — везде одинаковая .Net 3.5.
Сравнивалось два подхода, т.е. сравнивать нужно функции на первом и втором графике для каждой из машин.
Разные машины приведены в общем-то для расширения кругозора (все равно они в стойках стоят и на праздниках бездельничают)
В любом случае — сравнение не в пользу АМД — серверный процессор от Интела тоже участвовал :)
Thread это уж точно не процесс
Thread — это всегда нить. Process обозначается словом «процесс». Путать эти понятия не стоит. Разницу я думаю вы и так знаете :)
UFO just landed and posted this here
Темой моей курсовой работы было «Реализация многопоточности в .Net». Хочу выложить на хабр, но не хватает кармы…
Для персонального блога хватает, а для коллективного вам ещё кто-нибудь подбросит плюс, я уверен :)
Спасибо автору за статью, спасибо Вам за карму. Планирую заняться после сессии.
------простые числа на питоне--------------
#!/usr/bin/env python
import threading

thr = 100
sim = 10000
s = 3
S = [1,2]
def simple(n) :
    for d in range(2,n) :
        if n%d :
            if d == n-1: S.append(n)
        else : break

while s < sim :
    if threading.activeCount() <= thr:
        threading.Thread(target=simple, name="t%i" % s, args=[s]).start()
        s += 1

print S


выполняется буквально несколько секунд на интеле 4 в debian
рад и удивлен))
Ну, несколько секунд для простых чисел до 10к — это как-то не очень быстро…
def good_prime©:
    """Возвращает список простых чисел, найденный
методом "решето Сундарама" """
    #c=time.clock()
    D=C/2
    B=C/6
    A=set(range(D))
    for i in xrange(1,B+1):
        for j in xrange(i,(D+i)/(1+2*i)+1):
            A.discard(i+j+2*i*j)
    A=[ 2*x+1 for x in A ]
    #print time.clock()-c
    return A

А так? :)
«Очень» оптимальная программа — много лишних итераций как в главном цикле, так и в функции.
1) в главном цикле можно перебирать только нечетные числа
2) в функции перебирать нечетные, от 3 до n/2 с шагом 2 ( d in range(3, n//2, 2) )
комментарий к первой программе
Интересно было бы на Erlang посмотреть в такой же ситуации :) Не займетесь?
В данном случае выигрыша не будет. Скорее всего, Erlang будет медленнее из-за динамической типизации.
А вот не скажите. Все зависит от реализации. К тому же «динамический язык» не значит «медленный язык». Скажем, меня жутко удивило, что Dolphin Smalltalk считал некоторые тесты (кажется простые числа там тоже были) сопоставимо а то и быстрее альтернатив.

Хотя сами разработчики Dolphin-а говорят (и я с ними согласен) что целочисленные тесты для таких дел это зло и не могут являться критерием скорости языка. В том смысле, что реальные данные появляются в реальных же, боевых задачах, где автоматическая оптимизация кода скажет свое слово.
Конечно. Но реализация Erlang пока одна и мы все её знаем :)
Разумеется :) Я всего лишь попытался посмотреть с другой стороны
На той же википедии (на заметку)

За нахождение простого числа из более чем 108 десятичных цифр EFF назначила награду в 150000 долларов США.
Код не выложили, Parallel Extensions навряд ли юзали, так что ядро вы использовали скорее всего одно. Хотелось бы видеть также результаты после использования NGen'а. Конфигурации серверов не указаны(интересует конкретные процессоры и оперативная память). На другие косяки вам тоже указали. В общем очень скользкий тест, который стоит провести более честно;)
Sign up to leave a comment.

Articles