Experimental chill

Недавно мы потратили несколько дней, чтобы найти memory corruption в C++ коде. Оказалось это была плохая сортировка.

В общем, пропозал, который все точно ждали. Давайте проверять в сортировке strict weak ordering на первых X элементов. Про квадратичный алгоритм проверки я уже писал, надо дотащить до конца и для всех.

Квадратичный алгоритм находит больше багов, кубический алгоритм даже на 100 элементах будет достаточно дорого обходиться, а вот квадратичный самое то. Сортировки >100 элементов в реальной жизни достаточно редки, чтобы в них поставить баг и не заметить.

В общем, можете почитать RFC в LLVM:
https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217

Telegram

Experimental chill

Когда вы находите минимум/сортируете/делаете кучу из элементов, нужно чтобы ваши элементы удовлетворяли свойству строгого слабого порядка (по-английски strict weak ordering).

Этот порядок для компаратора comp и множества S означает несколько свойств:

1.…

www.group-telegram.com/tr/experimentalchill.com/241

10.9K viewsedited  Apr 27, 2023 at 09:35

Недавно мы потратили несколько дней, чтобы найти memory corruption в C++ коде. Оказалось это была плохая сортировка.

В общем, пропозал, который все точно ждали. Давайте проверять в сортировке strict weak ordering на первых X элементов. Про квадратичный алгоритм проверки я уже писал, надо дотащить до конца и для всех.

Квадратичный алгоритм находит больше багов, кубический алгоритм даже на 100 элементах будет достаточно дорого обходиться, а вот квадратичный самое то. Сортировки >100 элементов в реальной жизни достаточно редки, чтобы в них поставить баг и не заметить.

В общем, можете почитать RFC в LLVM:
https://discourse.llvm.org/t/rfc-strict-weak-ordering-checks-in-the-debug-libc/70217

BY Experimental chill