Jump to content

    

sigmaN

Свой
  • Content Count

    2644
  • Joined

  • Last visited

Community Reputation

0 Обычный

About sigmaN

  • Rank
    I WANT TO BELIEVE
  • Birthday 05/08/1986

Контакты

  • Сайт
    http://
  • ICQ
    300309333

Recent Profile Visitors

7049 profile views
  1. Не так драматически. Не знаю как это мы видим? )) Лично у меня классическая рекурсивная реализация проигрывает как по скорости, так и по требуемой памяти. И вообще считаю, что если есть требования к скорости и есть возможность что-то реализовать не рекурсивно - нужно реализовывать не рекурсивную версию. Но да ладно, перейдем к делу. Вчера вернулся я к этой задаче. Думал, гадал... туда-сюда код вертел... Ускорения особого добиться не удалось. Сдаюсь, думаю. Пойду смотреть как stable_sort реализован в STL. Входная последовательность разбивается на группы по 32 элемента Каждая такая группа сортируется сортировкой вставкой(insertion sort) После этого начинаются объединения(merge) Так что стало ясно, что алгоритм просто другой. Я "по честному" сливаю всё начиная от групп по 1 элемента, а там всё начинается с групп по 32. Еще потом посмотрю, может мелкомягкие еще какие-то хитрости используют ))
  2. Алгоритм merge sort не корректно сравнивать с quick sort потому как merge - это стабильная сортировка(сортировка, которая не меняет относительный порядок сортируемых элементов, имеющих одинаковые ключи). quick таким свойством не обладает. Ответ на вопрос зачем можно встретить уже в названии топика. Ну и далее я на него неоднократно отвечал.
  3. Сравнение сделаю. Скорее всего там реализована не merge sort, а quick sort. За merge sort вроде как нужно идти к std::stable_sort но и то без гарантий, как мы понимаем. https://stackoverflow.com/questions/5038895/does-stdsort-implement-quicksort Студию обновил до 2019. Вообще лично мне больше хотелось не просто поставить рекорды скорости, а именно разобраться что к чему с кешами и так далее, в плане оптимизации быстродействия. Вот, добился ускорения, измерил. Можно воспринимать эти цифры как относительные измерения, не абсолютные ) Add: std::stable_sort(arr, arr + N); Array = 100000000 elements, sizeof() = 400000000 Timer = 3911853us (3.911853sec) std::sort(arr, arr + N); Array = 100000000 elements, sizeof() = 400000000 Timer = 2681706us (2.681706sec) Add2: беглое чтение реализации stable_sort показало, что merge sort там используется. Правда через несколько условий которые я не проверял. Для маленьких массивов меньше 32 элемента используется insertion sort для остальных разные варианты merge sort в зависимости от доступности временного буфера. Почитаю там потом внимательнее что происходит у них. Пока интересно самому по-оптимизировать, а не копировать подсмотренные решения. Add3: сравнение компиляторов студии 2013 и 2019 различий в скорости моей реализации не показало.
  4. На сколько я помню, реализация библиотеки Си для AVR имеет после main() бесконечный цикл. Возврат в ResetHandler не производится, потому как из него и не происходит вызова. Вместо вызова делается просто jmp куда надо - т.е. на начало стартап кода, который подготавливает Си окружение и прыгает в main(). Убрать из main бесконечный цикл и посмотреть в отладчике что будет дальше не составляет никаких проблем. Более того - этим способом можно посмотреть даже на то, что происходит ДО main. Нужно только поставить брэйкпоинт на reset handler и шагать по инструкциям.
  5. Или я вас не понял или вы сделали неправильный вывод из расчетов. Я мыслю так: Внутренний цикл сорта в итоге копирует весь массив, посредством вызова merge() нужное кол-во раз. Давайте упростим и забудем про сравнения. Нам 381.4МБ через шину памяти надо протолкнуть 28 раз, умножаем на 2, потому как чтение+запись. Итого 28*381,4*2 = 20,8ГБ. Вы утверждаете, что DDR3-1333 может около 11ГБайт/с. Таким образом, если бы мы сидели на памяти, то потребовалось бы 20,8 / 11 = 1,89сек. О том, что сейчас мы сидим на процессоре, а не на пропускной способности памяти говорит и тот факт, что изначально потребовалось 8 секунд, а правка merge() касающаяся только кол-ва условных переходов в цикле, дала ускорение до 4.75сек. При этом ни кол-во обращений к памяти ни размеры прокачиваемых через неё данных не изменилось, поскольку алгоритм сортировки не менялся и изменен быть не может (иначе это уже будет реализация не merge sort, а чего-то другого). Считаю, что только после того, как процессор сможет всё сделать за 1,89сек мы упремся в память и как бы я не оптимизировал код - ускорения наблюдаться не будет. Т.к. пропускная способность памяти действительно закончится, а требование переслать туда-сюда нужное кол-во байт никуда не исчезнет (см. выше про то, что это всё-таки merge sort и он должен им оставаться). Правильно ли я рассуждаю?
  6. Были проведены измерения на массиве 100'000'000 элементов. Размер примерно 400 мегабайт. Для более консистентных результатов new был заменен на временный массив(static глобальная переменная, такая-же, как и сортируемый массив). Перед сортировкой массив заполняется отсортированной в обратном порядке последовательностью. Время выполнения измерялось через QueryPerformanceCounter() перед и после вызова функции сортровки. i7-2630QM DDR3-1333 dual channel, Visual Studio 2013 флаги компилятора /Ox /Ot /Oy Исходная реализация(код в первом посте, new заменен на статический временный массив). Array = 100000000 elements, sizeof() = 400000000 Timer = 8241447us (8.241448sec) Модифицированная реализация быстрее на 43%: Array = 100000000 elements, sizeof() = 400000000 Timer = 4759489us (4.759489sec) Модификации подверглась только функция merge(), её новая реализация под спойлером. Если кратко, то разные условные переходы были по максимуму вынесены из цикла. Из полученных результатов я сделал вывод, что узким местом была не память, а процессор. Хотя изначально казалось, что т.к. между доступами к памяти нет никаких особых вычислений то упрёмся мы в любом случае в память и несколько if() туда-сюда "погоды не сделают". Это оказалось не так. Продолжу исследовать эту тему. Пока что посмотрел эти два видео https://youtu.be/Nsf2_Au6KxU https://youtu.be/WDIkqP4JbkE Потом еще раз почитал PDF со слайдами Scott Meyers: Cpu Caches and Why You Care https://www.aristeia.com/TalkNotes/codedive-CPUCachesHandouts.pdf
  7. Сильное заявление... На сколько мне известно, они обычно применяются после того, как выбран наиболее быстрый(в классическом понимании этого слова) алгоритм. Почитаю,посмотрю. Но общее представление о работе подсистемы памяти у меня есть. Я даже несколько лекций Александреску смотрел в оригинале. Где про высоконагруженные системы и про то, что бесконечный цикл лучше цикла с условием, сравнивать лучше с нулем, не располагать bool в структурах, которые должны быть горячими в кэше и так далее... О том, что выделение памяти это дорого мы в курсе. Если бы функция сортировки вызывалась в программе достаточно часто, а максимально возможный размер массива был бы заранее известен то я бы выделил память один раз и вертел всё там. Пока что не ясно как применить всё вышесказанное к алгоритму сортировки слиянием, который я реализовал выше. Пока что мне кажется, что по памяти я всегда хожу линейно. Читаю всегда из одного массива - пишу в другой. Кэшу и блоку предсказаний процессора все карты в руки - пусть грузит в кеш память наперед, как только сообразит, что как минимум по чтению я по памяти всегда иду линейно от меньших адресов к старшим. Ну наверно можно было бы двигаться на одном проходе на повышение адресов, а на другом проходе на понижение. Из соображений, что недавно записанные данные по стершим адресам сейчас "горячие" и двигаясь обратно от них мы попадем в кеш. Или я как-то неправильно мыслю?
  8. Приветствую! Господа, оцените пожалуйста мою не рекурсивную реализацию сортировки слиянием. Покритикуйте, оцените )) Чисто спортивный интерес. Прочитал описание алгоритма, запилил с нуля ради разминки мозга. Основная "фишка" в том, что в отличие от рекурсивной реализации требуется меньше памяти как по объему так и по кол-ву выделений. Один раз происходит выделение временного массива, равного по размеру исходному, далее массивы переключаются по очереди и происходит слияние групп из одного в другой. Размер группы увеличивается в два раза за проход внешнего цикла. В общем то всё то-же самое, что и в рекурсивной реализации, только немного быстрее и экономнее по памяти. P.S. ясно, что рекурсивную реализацию в принципе тоже можно докрутить до однократного выделения памяти и работы уже из неё, но речь не о том. void merge(int* dst, int dstSize, int* left, int leftSize, int* right, int rightSize) { int leftIdx = 0; int rightIdx = 0; //printf("merge(dstsize=%i, leftsize=%i, rightSize=%i)\n", dstSize, leftSize, rightSize); for (int i = 0; (i < dstSize) && ((rightSize - rightIdx > 0) || (leftSize - leftIdx > 0)); i++) { //left array was exhausted, merge from right if (leftSize - leftIdx == 0) { dst[i] = right[rightIdx]; rightIdx++; } //right array was exhausted, merge from left else if (rightSize - rightIdx == 0) { dst[i] = left[leftIdx]; leftIdx++; } //both left and right still have elements to merge else { if (left[leftIdx] < right[rightIdx]) { dst[i] = left[leftIdx]; leftIdx++; } else { dst[i] = right[rightIdx]; rightIdx++; } } } } void mergeSortNonRecursive(int *a, int arrSize) { int *a2; try { a2 = new int[arrSize]; } catch (const std::bad_alloc& e) { printf("Bad alloc in mergeSortNonRecursive(): %s", e.what()); return; } int *arrays[2] = { a, a2 }; int arrayIdx = 0; int nextArrayIdx = (arrayIdx + 1) % 2; int groupLen = 2; int leftOffset; int leftSize; int rightOffset; int rightSize; int destOffset; int destSize; do{ leftOffset = 0; leftSize = 0; rightOffset = 0; rightSize = 0; destOffset = 0; destSize = 0; for (int i = 0; i < arrSize; i += groupLen) { destOffset = i; leftOffset = i; leftSize = arrSize - i; if (leftSize > groupLen / 2 ) leftSize = groupLen / 2; rightOffset = leftOffset + leftSize; rightSize = groupLen - leftSize; if (rightOffset > arrSize - 1) rightSize = 0; else if (rightOffset + rightSize > arrSize - 1) rightSize = arrSize - rightOffset; destSize = leftSize + rightSize; //printf("destOffset=%i, leftOffset=%i, rightOffset=%i\n", destOffset, leftOffset, rightOffset); merge(arrays[nextArrayIdx] + destOffset, destSize, arrays[arrayIdx] + leftOffset, leftSize, arrays[arrayIdx] + rightOffset, rightSize); } arrayIdx = nextArrayIdx; nextArrayIdx = (arrayIdx + 1) % 2; groupLen = groupLen * 2; } while (groupLen <= arrSize); //doing final merge if needed if (destSize != arrSize) { //printf("doing final merge\n"); rightSize = destSize; rightOffset = arrSize - rightSize; leftOffset = 0; leftSize = arrSize - rightSize; destOffset = 0; destSize = arrSize; merge(arrays[nextArrayIdx] + destOffset, destSize, arrays[arrayIdx] + leftOffset, leftSize, arrays[arrayIdx] + rightOffset, rightSize); arrayIdx = nextArrayIdx; nextArrayIdx = (arrayIdx + 1) % 2; } //copy result to a[] if it is not already there if (arrayIdx != 0) { for (int i = 0; i < arrSize; i++) a[i] = arrays[arrayIdx][i]; } delete[] a2; }
  9. Нашел калькулятор от TI http://webench.ti.com/wb5/LDC/?DCMP=ldc&amp;HQS=sva-psp-ssp-ldc-awire-20150819-lp-webenchcoil-wwe#/spirals Почему-то он рекомендует не заполнять катушку более чем на 70% Говорит, что Coil fill ratio должно быть больше 0.3 Почему так? Какой физический принцип, лежит в основе этой рекомендации? Просто это ограничение идет немного в разрез с желанием намотать по-больше витков.
  10. Я так понял, мне надо сделать по-больше витков, заказать плату, а потом просто измерить индуктивность, посчитать номиналы деталей по аппноте и всё будет ок.
  11. Нашел аппноту https://www.emmicroelectronic.com/sites/default/files/products/datasheets/an404.pdf на страницах с 5 по 8 даётся информация по подбору нужных номиналов и ограничения разные(по току через ключи и так далее). Они исходят из заранее заданных параметров антенны: Индуктивность 300uH to 800uH Добротность в районе 40 На стр.7 приведен расчёт резонансного конденсатора.... Правильно ли я понимаю, что если в качестве f0 принять необходимую нам частоту == 125КГц, а индуктивность La измерить, то потом автоматически получится, что если такой конденсатор Cres подключить к катушке с индуктивностью La то резонансная частота колебательного контура и будет те самые 125КГц? От чего тогда будет зависеть добротность? Как её повысить? Нарисовать на плате больше витков в принципе то не проблема, хочется с пониманием подойти к этому процессу просто.
  12. Добрый день. Есть желание сделать антенну как на фото, но нет желания слепо копировать чужую плату. Это RFID ридер на 125КГц. Как такие вещи рассчитываются? Может быть есть какой-то софт? Плата на фото имеет спиральную дорожку с обеих сторон. Я вижу, что кол-во витков очень разное бывает...
  13. Это понятно. Из LLVM можно взять фронтэнд какого-то языка, оптимизацию и написать только интерпретатор для микроконтроллера и бэкэнд для LLVM. Есть еще одна мысль: Раз уж запуск каких-то компиляторов на стороне ПК это не проблема, то почему бы не использовать С/С++ компилятор для вашего микроконтроллера для превращения вашего "скрипта" в нативные инструкции? Ваши "скрипты" превращается в функции. Их будет конечное кол-во(с заранее заданными именами). Основная прошивка будет их вызывать в нужных местах, передавая в качестве первого параметра указатель на некое глобальное состояние(структуру), с помощью которой ваш скрипт может взаимодействовать с основной прошивкой. Дальше можно по-фантазировать... Либо заранее зарезервировать под каждый такой скрипт определенное имя и кол-во байт, либо из основной прошивки за скриптом обращаться к некому менеджеру, который по запросу передаст выполнение нужному скрипту(кодировка скриптов по значению int переменной), тогда снимаются ограничения на кол-во и размер каждого из таких "скриптов". Из плюсов такого нативного подхода: +Стандартный, всем известный и понятный язык программирования +Возможность отделить защищенную основную прошивку от этих доп.модулей(скриптов) +Нативный код, все оптимизации нативного компилятора Минусы -Возможные проблемы с безопасностью. Надо думать, как ограничивать этому куску нативного кода доступ к памяти, чтобы он не с дампил вашу основную прошивку злоумышленникам. Есть ли вообще такая проблема и задача у вас? Наверно этот вопрос может быть решен путем анализа области памяти со "скриптами" и выявления там инструкций, которые пытаются получить доступ к чему-то запрещенному (запрещенный диапазон адресов например). Так можно ограничить доступ и к оборудованию и к памяти... Но, это вопрос дискуссионный. Сходу, без серьезного анализа, за безопасность такого решения я бы отвечать не стал )) Но, вроде как, это довольно не сложный анализ должен быть(со списком запрещенных инструкций). Скрипт, заподозренный в чем-то не хорошем, просто помечается как опасный и из основной прошивки управление ему не передаётся. Надо еще как-то хитро ограничить доступ к запрещенным областям памяти по указателям.... В общем, над безопасностью нужно хорошо подумать )