Close Topic Options

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

Родственник мой, S., оказался в Америке в начале восьмидесятых, в возрасте "за сорок" и владея английским языком в рамках "средней школы давно". Помыкавшись некоторое время (не о том сказ), S. нашел отличную работу - программистом Больших Шкафов для телефонного гиганта AB&C (кто знает, тот поймет). Для общения с начальством новоиспеченный программист быстро выучил английскую фразу "летмишоую" (сейчас покажу), за которой следовала демонстрация работающего кода, и вопросов больше не возникало.

Работа в телефонных гигантах неторопливая, но S. бездельничать не любил, и решил заняться оптимизацией. В одном из Больших Шкафов обнаружилась база данных, а в ней - таблица с парами чисел: 1-3, 2-6, 3-9, ... , 1000000-3000000. Ничтоже сумняшеся, S. таблицу стер, а обращения к ней заменил строчкой B=Ax3. Шкаф, радостно заурчав, продолжал функционировать. Отсутствие таблицы начальство заметило (и то по чистой случайности) через неделю. Состоялся знаменательный диалог:

- Где таблица?
- Таблица не нужна.
- Как это не нужна?
- Ну, не нужна. Летмишоую. Вот: B=Ax3
- Что это?
- Вместо таблицы.
- А где таблица?
- Я ее стер. Не нужна.
- Как стер???
- Летмишоую. Вот, работает. B=Ax3
- Ну, работает. А где таблица-то?
...
В конце концов, проявив завидную корпоративную мудрость, начальник оставил S. в покое. А по AB&C долго ходили легенды о сумасшедшем бородатом русском, который ПРИДУМАЛ ФОРМУЛУ.

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

а) не в случае умножения на 3 там туевая хуча не такая уж у туевая.
б) поиск по таблице из миллиона записей тоже далеко не дешевая операция.

Я эту историю слышал и про таблицы, где надо было умножать на 5 и на 7 и т.д. В принципе, все просто, но поиск в любой таблице всяко быстрее. Ты же просто берешь данные по адресу, смещение которого от базы равняется аргументу.

<злостный офтопик>
когда смещение составляет миллион, то это уже далеко выпрыгивает за пределы сегмента. Более того, такими числами в то время тоже оперировать было не так просто, они в регистр не лезли. Всё очень зависит от оптимизатора кода, но в описанном варианте (умножение на 3, таблица из миллиона элементов) похоже, что умножение таки более дешевая операция.

P.S. А с делением всё гораздо сложнее.
</злостный офтопик>

Не сразу заметил, но если уж конкретно в данном описанном варианте, то:

Запрос к базе данных (какой бы embedded она ни была) всяко не будет быстрее умножения.

<злостный офтопик>
когда смещение составляет миллион, то это уже далеко выпрыгивает за пределы сегмента. Более того, такими числами в то время тоже оперировать было не так просто, они в регистр не лезли. Всё очень зависит от оптимизатора кода, но в описанном варианте (умножение на 3, таблица из миллиона элементов) похоже, что умножение таки более дешевая операция.

P.S. А с делением всё гораздо сложнее.
</злостный офтопик>

Сегментация памяти существует далеко не на всех компьютерах. Если брать х86/x80 систему, то я с тобой согласен. Если брать, скажем, ARM7, то нет. Хотя трудно поверить, что те машины были собраны на ARM.
В общем, пусть Damballah разузнает параметры той машины и мы с тобой будем разговаривать аргументированно

obaldin

Не скажи. Если БД представляет собой просто индексную таблицу, то доступ к ней будет всяко быстрее умножения.

Сомневаюсь - по двум пунктам. Во-первых, хотя БД и не обязательно RDBMS со всеми сегодняшними фишками, но все же не очень вероятно, чтобы простую таблицу в памяти назвали бы БД. И второе - если у тебя на машине байтовая адресация, то для доступа к таблице тебе уже придется умножить индекс на размер ячейки. Хотя, конечно, остаются словные адресации и прочие фишки. И третье - если речь идет о старой технике, то пара мегабайт в памяти - это серьезно, вряд ли бы про них просто "забыли".

В целом же, для меня эта история (если считать ее правдивой, конечно) будет не о превосходстве "русского программиста", а просто очередная "war story" о "maintenance programming". Скажем, была когда-то сложная функция, в коде. Потом пришел другой программист и, в целях оптимизации, вынес расчет функции в отдельную тулзу и таблицу. Потом, много времени спустя, пришел maintenance-программист, которому велели изменить формулу на x*3. Что он и сделал в лучших традициях - минимальное изменение, которое работает. Оптимизировать дальше, с риском сломать, он не стал. В общем-то, когда речь идет о системах в многие миллионы строк кода, и с огромной ответственностью - я его прекрасно понимаю.

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

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

Сомнительной представляется также идея о таком нерациональном использовании (23Мбита минимум, без компрессии) памяти на древней машине, особенно, если учесть, что еще в конце 80-х годов 8МБайт на мейнфрейме считалось круто. Если же эта память находится в дисковом/ленточном пространстве, то эта таблица вообще не имеет смысла, ибо умножение будет явно быстрее.

Так что, без возможности узнать а) тип процессора, б) местонахождение БД и в) тип БД, говорить о чем либо сильно проблематично.

Что касается самого прикола, то я его воспринимаю, как очередную байку о том, что тупые америкосы нифига не понимают, а гениальный русский, знающий только "летмишоую" "сделал всех"
Думаю, что такие же рассказы ходят в среде китайцев и (вот ужас-то - индусов).


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

Не, давайте с начала.

Для умножения N на число надо поместить их в регистры, перемножить, и либо забрать результат из регистра, либо сразу использовать. Так?

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

Ну и объясните мне на пальцах, как работа с массивом в априори медленной памяти может быть быстрее обычного умножения? Я вижу только один вариант ускорения, когда идет работа с Arbitrary Precision числами, которые не влазят в регистр...

(Это я правда больше в адвоката дьявола поиграть, но все же...)

Зависит от аппаратуры. Например, на чем-то типа VAX'а это - одна машинная команда. Не знаю, была ли она быстрее умножения, но это возможно. Умножение было когда-то довольно дорогой операцией. Думаю, вполне очевидно, что описанные "телефонные гиганты" могли пользоваться самым изумительным хардвером, так что чем черт не шутит.

Лесорубы блин

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

Не, давайте с начала.

Для умножения N на число надо поместить их в регистры, перемножить, и либо забрать результат из регистра, либо сразу использовать. Так?

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

Ну и объясните мне на пальцах, как работа с массивом в априори медленной памяти может быть быстрее обычного умножения? Я вижу только один вариант ускорения, когда идет работа с Arbitrary Precision числами, которые не влазят в регистр...

Не так.

Для умножения N на число X надо сделать вот что (без привязки к конкретной архитектуре):
1. Загрузить N в регистр.
2. Загрузить X в регистр.
3. Выполнить команду умножения
4. Записать регистр в память.

Это в случае, когда в процессоре есть команда умножения. Ее может не быть!

Для перехода к N-члену массива надо выполнить следующую операции:
1. Загрузить в базовый регистр адрес начала массива.
2. Загрузить в регистр смещения N.
3. Загрузить N в регистр, используя типовую команду адресной арифметики (База+смещение).
4. Записать регистр в память.

Исходя из того, что на большинстве процессоров (кроме нескольких DSP, ADI Sharc, например - но там можно за один такт загрузить два регистра в память, кстати, если обращаться к двум банкам сразу), команда умножения занимает намного больше тактов, чем команда обращения к памяти (хотя тоже от памяти зависит, от ее типа, а также от контроллера), поиск в таблице всяко быстрее, чем умножение. А если учесть, что команды умножения может не быть (я, в общем-то, с этого и начал - см мой первый пост), то поиск в памяти намного быстрее, чем умножение.

Насчет китайцев не знаю. А насчет индусов... ты работал с ними? Не с теми, которые европеизированные, а с теми, которые в Индии программазмом занимаются?

VxWorks с индусами не работал. И я не программер. Зато беседовал с представителями минобороны Индии и Пакистана. Обычные люди. Разве что взгляд цепкий. Но у работников Шабака он не менее цепкий.
С китайцами работал, с корейцами, правда, недолго. Мой отец с ними уже больше года работает, на стройках в Израиле их куча. Отзывается неплохо.
Товарищ по армии жил в Южной Корее и Китае. Отзывы положительные.
Но насчет культуры ты не отрицаешь, это радует.