Discreet and not discrete.

Если у вас есть алгоритм на графах, попробуйте сформулировать его в терминах линейной алгебры и матрицы смежности. Например, clustering coefficients вычисляются через третью степень матрицы смежности с небольшой обработкой. Включая и алгоритм вычисления обновлений для изменений матрицы смежности.

Это приводит к простой возможности разделить данные на несколько машин, а также к возможности использовать разные эффективные алгоритмы работы с матрицами, включая оптимизированные алгоритмы умножения матриц (см. hypersparse matrix multiplication и SUMMA).

Здесь мы подходим к необходимости распознавать алгоритмы, записанные пользователем в DSL на циклах, допустим. Ну, это уже было украдено до нас, неоднократно.

Вся индустрия ПО о-ши-ба-ет-ся, особенно, та часть которая "я _________ (датасайнтист/доктор/инженер/финансист - подчеркнуть или вписать), а не программист". Как я уже рассказывал, Amgen обратился в ParSci за решением задачи корректности анализа статистических данных - треть медицинских статей содержала ошибки типа "у эксперимента 1 p=0.04, у эксперимента 2 p=0.038, поэтому мы считаем доказанной гипотезу эксперимента 2" (прямое сравнение p-значений). По идее, отрубив возможность сравнивать p значения напрямую (нет реализации Ord), мы, типами, ограничивали бы возможность допущения ошибок такого типа, получая из Хаскельного кода структуру анализа эксперимента и получения выводов. Они заказали у ParSci библиотеку подключения к R, для использования уже отлаженных и оптимизированных алгоритмов с улучшенными типами, но, как известно, работа ушла на сторону и появился Tweag (если я правильно понимаю).

В дни моего использования Data.IntMap он не был завязан на конкретное представление целого, как ключа. Поэтому его можно было перепилить под меньшее целое (например, 32 бита) и это радикально увеличивало производительность - и мусора меньше, и с кешем получше и, если это кто ещё не знал, 64-битная платформа лучше работает с 32-битными значениями. Поэтому разреженные матрицы связности я хранил в IntMap (IntMap a), что, в сумме позволило обогнать код на Си (clustering coefficients) в десять (10) раз по скорости.

Почему так?

Потому, что IntMap уже сортированные. И их пересечение имеет сложность O(n). При анализе безмасштабных графов вы в обязательном порядке зайдёте на узел со связностью O(количество узлов графа) - так уж устроены эти графы.

Код на Си использовал несортированное представление связности узла - он сперва копировал в буфер, потом сортировал и после выполнял пересечение для сортированных представлений. То есть, при старте с пустого графа выполнялось O(N) сортировок сложностью O(NlogN) для пересечений и O(N) вставок. В сумме сложность была O(N^2logN). При использовании сортированного представления на IntMap мы получаем O(NlogN) сложность вставок и O(N^2) сложность пересечений. Разница на графе в 16 миллионов узлов получилась в десять раз - то есть, код на Хаскеле был медленный (должно было получиться 24 раза), но всё равно быстрее Си.

Что самое приятное, я всё это проделал "не приходя в сознание" - взял сперва Data.Map, потом Data.IntMap, потом поменял ключ в IntMap и вуаля! получил довольно быстро работающую программу.

Вот, вроде, и всё.

PS
История с Tweag уточняется. Может быть, я неправильно помню.

Которая Рамен Хаус на Толстого.

За неделю у них уменьшились порции и выросли цены процентов на пять, такого плана.

Не рекомендую.

Был упомянут в посте shadow_ru, по поводу чего имею вот, что сказать.

Как известно, ум коррелирует с IQ, типа, чем умнее человек, тем выше IQ. В жизни же IQ практически наилучшим образом коррелирует с доходами - чем выше IQ, тем выше доход, и наоборот. Соответственно, он коррелирует с карьерным ростом, ибо там доход выше.

Интересное здесь то, что для карьерного роста необходимо уметь врать. Вообще, убеждать, но эти две вещи связаны.

Наилучший лжец верит в то, о чем врет. Умеет убедить, в первую очередь, самого себя.

После того, как до меня это дошло, я стал ловить моменты, когда такое происходит. Например, это отлично видно в отношении западных интеллектуалов к Трампу - вместо разбирательства, почему они не смогли понять его победу, они ретранслируют мнения, совпадающие с их плохим к Трампа отношением.

Так вот, Левенчук находится ровно в этой же позиции - достаточно умён, чтобы обмануть себя, что я и вижу.

Это не означает отсутствия знаний и умений, просто его слова надо проверять, как и мои, впрочем. Что-то может быть полезным, надо уметь увидеть.

Для меня, впрочем, полезной информации у него маловато, а труд такой же, как и при чтении 17ur.

Smalltalk в его инкарнации конце 90-х. выполнял одно очень правильное преобразование кода в своём JIT - специализацию.

Если в код часто приходил объект одного и того же класса (или, сильнее, с одним и тем же обработчиком сообщения, вызываемом из кода), то для этого условия выполнялась специализация кода с устранением виртуализации вызова.

Что порождало возможность развернуть вызываемый код и, далее, устранить проверки.

Это преобразование очень важно - вы пишите код в нужных абстракциях и вам его преобразуют в быстрый код, устраняя абстракции.

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

Вон, в моём коде использовался Counter, в который я всегда добавлял положительные счётчики. Куски кода Counter, которые проверяют на ноль и/или отрицательные значения, могли бы быть выброшены вообще, поскольку никогда не сработают. Но они выброшены не были и в результате замена Counter на dict и расстановка условий и циклов там, где я использовал one_counter += other_counter, привела к ускорению выполнения более, чем в десять раз.

Smalltalk, очень не статический язык, в его инкарнации начала 90-х, имел JIT, который умел убирать обращение к VMT. Это, потом, попало в HotSpot, если что.

Как так получилось, что современный Питон, со всеми вложенными в него деньгами, не умеет так делать до сих пор и мне до сих пор надо делать if key in dict: dict[key] = f(dict[key], x) else: dict[key] = g(x)?

Для этого даже JIT не нужен, если что. Это можно в байткоде делать и всё равно выигрыш будет.

PS
Отхожу от замены всех Counter обратно на dict, что дало увеличение скорости в 100 раз.

Наше текущее AST в трансляторе VHDL спроектировано изменяемым. Сперва создаётся объект через new ASTObject(tree и тп) и заполняется через вызовы методов и установку свойств. Обоснование изначально было "если мы не сможем создать объект полностью, так хоть частично его заполним и вернём".

Поскольку надо сигнализировать об ошибке, практически всюду и везде возвращается null. Частично созданный объект никогда не возвращается.

VHDL язык с недетерминизмом в проверке типов - если у нас есть "оператор" function "AND"(a,b:integer) return integer и function "AND" (a,b:integer) return bit_vector, то проверка типов должна попробовать оба-два варианта для выражения 1 AND x. Большую часть времени возвращаемый тип ограничен сверху, но иногда не ограничен - при преобразовании подтипов-массивов (подробности, право слово, ещё ужасней). Поэтому естественным подходом к проверке типов был бы "создаём все варианты, а потом отбросим ненужные", однако проверка типов сопряжена с созданием объектов AST (и это верно, ибо x(a) может быть вызовом функции или взятием элемента массива), а они, как я уже объяснил, сперва создаются, потом заполняются и меняются в процессе. Поэтому правильный подход затруднён, если учесть размер функций преобразования - в районе 50-600 строк, медиана сотня строк.

Но и это ещё не всё.

В данный момент все файлы транслируются каждый раз перед запуском. Причина проста - запомнить состояние проекта невозможно, ибо, бахама мама, AST может быть изменено! Да и система поиска прошита в AST так, что отделить её от самой AST труднее, чем сиамских близнецов, сросшихся сердцами. А при компиляции изменённых файлов надо же ещё перекомпилировать файлы, которые зависели от содержимого изменившихся!

Опять же, если бы 1) использовались неизменные данные (readonly на все поля) и 2) система поиска была бы отвязана от AST и делалась бы атрибутными грамматиками (точнее, атрибутными деревьями - деревья AST, дополненные атрибутами), то обе вышеописанные проблемы были бы не то, что решаемы, а имели бы тривиальное решение.

Но я живу в мире, который мне дан в ощущениях (а не выбран мной), поэтому я буду лопатить тонны кода, преобразуя сие чудо техники в нечто нормальное, пока ответственный за всё это рисует платы в нашем CAD.

А вот мои читатели, надеюсь, учтут эти ошибки и смогут их обойти.

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

Если вам дали задачу перед интервью, попросите ваших будущих интервьюеров решить задачу К: http://thesz.livejournal.com/280784.html

Ну, чтобы было интересней на возможном интервью. ;)

А то что это такое - вас изучают активными пробами, а вы играете пассивную роль "черного ящика".

Общение началось с фразы "Крайнее место работы у вас..."

Выпуск ASIC в 2007 году стоил ~$250K пробный образец. Зарплата у инженера была $2,5K, такого плана.

Сейчас выпуск ASIC это небольшие миллионы долларов - никто током не умеет считать столь мелкие нанометры, моделей быстрых нет. Уже с 45 нм на задержку влияла не только длина проводника, а и количество поворотов. Эти миллионы долларов это либо обсчёт, либо парочка выпусков пробных образцов.

Так вот, когда у инженера, отвечающего за формальную верификацию микросхемы, зарплата 200 тысяч рублей ($3K), это не то, что плохо, это рецепт провала.

Вот, откуда позвонили: https://ru.wikipedia.org/wiki/Topcon

Когда любишь, то о любимой думаешь. Думая о ней, становишься лучше - больше понимаешь, и это самое малое. Когда в мыслях возвращаешься к любимой, к местам и временам, проведённым вместе, невольно стараешься сделать так, чтобы будущее стало лучше.

Или, переводя эту поэззию на низкий язык рассуждений, совершая повторения выученного, стараешься стать лучше - точнее выражать чувства или, как должно было быть в случае одного программиста, повторяешь и сводишь воедино разные решения и задачи.

То есть, если любишь программирование, то думаешь о нём. Думая о нём, становишься лучше. Становясь лучше, можешь больше, вплоть до написания имени любимой в пыли Луны.

А не заявляешь "я фронтэнд девелопер (whatever that means)" и ждёшь, что перед тобой расстелят красную дорожку.

Я сейчас поддерживаю и развиваю компилятор VHDL, оставленный мне в наследство руководителем, сделавшим AST не типизированным, программистом, делавшим всё "на отвалите от меня" и бывшим инженером-электронщиком. Последние два уволились. Поверх VHDL мне надо добавить поддержку Верилога.

То есть, к безумию стандарта VHDL добавляется интересность суммарного подхода бывших разработчиков.

Так вот.

Сейчас я перевёл разбор VHDL на ANTLR4 и собираюсь сделать систему по сведению типизированного (на классах) и нетипизированного (на деревьях деревьев/лексем) AST воедино.

В результате у меня есть проверка регрессии - AST разошлись, нет? - и возможность постепенно переходить на нормальный подход (с типами, а не один ITree на всё про всё).

Я начинаю считать себя суперпрограммистом. Если я со всем этим разберусь, то я буду круче всех известных мне программистов вообще. Поддержка и развитие безумного старого стандарта с использованием и исправлением кода, написанного, частично, инженером-электронщиком и, частично, человеком, которым "немного вредил" - что может быть страшнее?

(подробности тянули на три часа набивания и редактирования поста)