caxapa.ru :: Средний ПК ищет максимальное за

Tpoeшник (10.02.2021 15:14, просмотров: 644) ответил Tpoeшник на Си. AVR. Ищу самый быстрый во вселенной алгоритм поиска максимального числа в огромном массиве char.

Средний ПК ищет максимальное за

1000000 - 2.987ms 400000 - 1.8292ms 40000 - 1.153899ms 4000 - 0.1188ms 2000 - 0.067001ms 1000 - 0.045599ms

АВР 1000000 в лучшем случае 46ms. Это ХМега на 64МГц и 3 такта. Можно конечно настроить ДМА чтоб из ОЗУ загружал в пространство IO но и даже если получится все то будет 64/3 что значительно медленнее ПК.

Ответить

- С каких пор ХМега на 64МГц работает? Она же всегда на 32МГц работала? - Ale3000(12.02.2021 08:00)
  - Работает, разгоняют. - Tpoeшник(12.02.2021 09:34)
    - Вопрос от пиковода. Эти ваши 64 МГц - частота генератора или количество команд в секунду? - Kpoк(12.02.2021 10:57)
      - Я так понимаю что если команда выполняется за один такт, то 64млн в сек команд. - Tpoeшник(12.02.2021 13:02)
        
        Вот это "если" смущает. А сколько тактов вообще занимают команды как правило? - Kpoк(12.02.2021 13:16)
        
        Большинство команд исполняется за 1 такт, иногда за 2 и несколько за 3 и единицы за 4 :)) ещё зависит от семейства: На "иксмегах", к примеру, некотрые инструкции выполняются быстее, чем на "мегах" или "тайнях". - Adept(12.02.2021 13:31, ссылка)
        
        все кроме команд ветвления и аппаратного умножения выполняются за один такт, переходы могут занимать и 4 такта )) - Aleksey_75(12.02.2021 13:20)
        
        Ну не только. Некоторые косвенные обращения к памяти через X, Y, Z требуют два такта - LightElf(12.02.2021 13:26)
        
        это детали. Главное, что в основном по 1 такту. Быстрее, чем ПИКи, мля. - Kpoк(12.02.2021 13:41)
        
        в этом плане AVR вне конкуренции - Aleksey_75(12.02.2021 13:49)
        
        угу! - Aleksey_75(12.02.2021 13:26)
    - Если разгонять можно, берите толстую плисину и накатывайте корку, вот тут клевущут ~300 МГц >>> SciFi(77 знак., 12.02.2021 09:54, ссылка)
      - Что интересно, ядро SH2 всего вдвое толще AVR. - LightElf(12.02.2021 11:35)
        
        Дык Троешнику давно намякивают, что он не на ту клячу поставил :-) - SciFi(12.02.2021 11:36)
        
        Для Троешника есть совсем няшная цацка - LightElf(12.02.2021 11:52, ссылка)
        
        Кнута раскулачили? - Kpoк(12.02.2021 14:14)
        
        теперь дайте к нему конпелятор! - Mahagam(12.02.2021 13:35)
        
        Там ассемблер есть. Писать несложно должно быть - всего 4 команды у процессора. - LightElf(12.02.2021 14:05)
        
        даже у брейнфака команд побольше будет. несложно, ага. - Mahagam(12.02.2021 14:46)
        
        Спасибо. Ничего не понятно, но документ конфетка. Шрифты, отступы, ммм - Tpoeшник(12.02.2021 12:00)
        
        Это заначка на случай ядерной войны. Как сделать проц на транзисторах КТ315. - SciFi(12.02.2021 12:02)
        
        Done. Можешь начинать изучать - Evgeny_CD(12.02.2021 12:32, ссылка)
        
        Где-то в начке валяется MAX7064S, можно попробовать упихать :) - LightElf(12.02.2021 12:06)
    - внешним тактом? - m16(12.02.2021 09:41)
      - Я не разбираюсь в этом вопросе. Знаю что работает - Tpoeшник(12.02.2021 10:28, ссылка)
- Я правильно понимаю, чт АВР выполняет операцию выборки-сравнения-замены-инкремета адреса быстрее чем за одну команду? Код в студию! - Kpoк(11.02.2021 09:11)
  - вот :) --> - Adept(11.02.2021 13:27, ссылка)
  - Три команды вроде как. На 64Мhz это быстро. 46ms - 1млн записей - Tpoeшник(11.02.2021 10:59)
    - Кто разучился считать? - SciFi(11.02.2021 11:05)
      - Вероятно я? А как нужно? Tpoeшник(170 знак., 11.02.2021 11:19)
        
        По большому счёту, какая разница? Но когда считаете деньги, делайте это тщательно. - SciFi(11.02.2021 11:21)
        
        Разница? Для меня есть. Если три команды на один элемент то на 64 млн команд в секунду можно перелопатить 21млн с копейками. Или я не правильно понимаю как соотносятся скорости и команды проца? Спс - Tpoeшник(11.02.2021 11:33)
        
        Это я торможу. Прошу пардону. - SciFi(11.02.2021 11:40)
        
        Тогда в качестве жеста справедливости подскажите как работает команда std Tpoeшник(36 знак., 11.02.2021 11:50)
        
        std y+r17,r17 есть неверно m16(1 знак., 11.02.2021 12:04, картинка)
        
        Спасибо - Tpoeшник(11.02.2021 17:09)
        
        держи буку m16(11.02.2021 19:16, ссылка)
        
        Спасибо! Есть такая в бумажном виде. - Tpoeшник(11.02.2021 22:59)
- У меня скриптовый язык считает в 4 раза быстрее вашего "среднего ПК" 1000000@0.644775ms - lloyd(10.02.2021 20:34, ссылка)
  - Код с SSE работает примерно в 1000 раз быстрее LuaJIT - lloyd(10.02.2021 21:46, ссылка)
    - Я не понимаю. Напишите сколько ПК тратит на 1млн значений в массиве в ms ну или us. 0.644775ms? Спасибо - Tpoeшник(10.02.2021 23:03)
      - С SSE4.1 он потратил на это 0.6 мкс. Суть в использовании SIMD инструкций, которые находят 16 максимумов за раз. - lloyd(11.02.2021 06:29)
        
        Там сразу вынимает 16 байт, и 16 компараторов сравнивают их с 16 опорами? - Kpoк(11.02.2021 10:24)
        
        ага. SIMD давно умеет в 128 бит. очень давно - Mahagam(11.02.2021 14:57)
        
        0,6 мкс на 1000000 значений? Это 0,6 пс на одно значение? У меня 2 вопроса: как я проспал терагерцы и какая там скорость памяти? - SciFi(11.02.2021 07:31)
        
        +1 - Tpoeшник(11.02.2021 09:20)
        
        Вообще может я и накосячил в коде, надо внимательнее глянуть. Но вообще весь мегабайт строки прекрасно помещается в кеш процессора (запускалось на intel xeon) - lloyd(11.02.2021 08:10)
        
        для работы из кеша вообще какой-то нереальный тормоз :( - Adept(11.02.2021 15:41)
        
        запускалось в виртуалке, вот - lloyd(11.02.2021 17:35)
- Какой-то шибко медленный ПК. Код можно увидеть? - LightElf(10.02.2021 17:43)
  - Можно Tpoeшник(428 знак., 10.02.2021 20:29 - 20:39)
    - А на асме вылизать? - LightElf(11.02.2021 17:47)
      - для этого есть специально обученный компилятор - Mahagam(11.02.2021 21:54)
    - Если вот здесь смотреть то результаты совсем плохие. Но из консоли с установленной средой данные выше приводил. - Tpoeшник(10.02.2021 20:30, ссылка)
      - Там же можно сишник запускать. - SciFi(10.02.2021 20:41)
        
        Да, но все плохо. Ну или я не понимаю. Tpoeшник(1 знак., 10.02.2021 20:53, картинка)
        
        Ну так измерения делают на больших кусках, чтобы краевые эффекты не мешали. - SciFi(10.02.2021 20:56)
        
        0.004242 на чистом 1000000 - Tpoeшник(10.02.2021 20:58)
        
        или вот >>> - SciFi(10.02.2021 21:17, ссылка)
      - жабаскрипт понад усе :-) - SciFi(10.02.2021 20:40)
- да не так уж и плохо :) берём блок 2K (именно столько есть свободного в достатке у иксмеги) исходим из скорострельности алгоритма 3 такта и клока 32МГц (штатно для иксмеги) = 2048*(3/32e6)=192мкс супротив 69мкс на ПК, т.е. соотношение 1:3 в пользу ПК при разнице клоков 1:100 (@3GHz в однопотоке) /про разницу в энергопотреблении и не говорю/ :)) Adept(186 знак., 10.02.2021 17:01, ссылка)
  - а где вы такой медленный x86 нашли?? - Mahagam(10.02.2021 17:38)
    - ТС выше пишет: - "Средний ПК ищет максимальное за... 2000 - 0.067001ms" - Adept(10.02.2021 17:43)
      - а цифры откуда взяты? а код под этот поиск также оптимизирован? Mahagam(1 знак., 10.02.2021 17:49, картинка)

Микроконтроллеры AVR