Реальные вопросы на собеседовании

я тебе даже больше скажу… берешь хештаблицу на тыщу элементов, ставишь на каждый по спинлоку и твои 64 треда не столкнутся там никогда…

Иди в дворники, маня.

Почему люки круглые

Все?

я тебе даже больше скажу… берешь хештаблицу на тыщу элементов, ставишь на каждый по спинлоку и твои 64 треда не столкнутся там никогда…

Пожалуйста, перестань писать код.

Пожалуйста, перестань писать код.

покажи свой :)

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

О - оверинжинирнг.

Иди в дворники, маня.

ну так какой у тебя приличный быстрый многопоточный хеш? ответа так и нет. допустим нет у тебя std::map - библиотечной палочки-выручалочки неясной эфективности поиска, вставки, удаления, как будешь действовать ты? ну вот как?

Я тут недавно задачу по теории вероятности видел. Она к собеседованиям наверно отношения не имеет, но задача - просто жесть, как мне кажется. Я до решения не догадался, конечно. Решение знаю, но до сих пор не могу в него поверить.
Вот эта задача.
Двум математикам предложили игру. Обоим дадут по симметричной монетке. Они свои монетки будут подкидывть и записывать результат, получая, таким образом, бесконечную случайную последовательность орлов и решек. Друг с другом математики никак взаимодействовать не смогут и не будут знать результатов бросков напарника. Суть игры в том, что им нужно будет назвать число - номер броска в последовательности напарника. Если результаты бросков под названными ими номерами совпадут - они выиграли. Если не совпадут - проиграли. Какую стратегию им выбрать, чтобы шансы выиграть были выше 50%?

как будешь действовать ты?

Я тебя, клоуна, заигнорю наконец.

О - оверинжинирнг.

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

Ну только твой «самый быстрый кеш» флашит кешлинию на взятии спинлока даже на чтении. А так нормально, да :D

Я тебя, клоуна, заигнорю наконец.

ты просто ответь. как будешь делать кеш без стандартной либы с++. вопрос простейший.

Ну только твой «самый быстрый кеш» флашит кешлинию на взятии спинлока даже на чтении. А так нормально, да :D

давай тот кеш который быстрее… один уже застрял.

Мы говорим про ориентированный на чтение? RCU.

выше 50%?

А так можно вообще?

Если результаты бросков под названными ими номерами совпадут

Т.е. один может сказать 1, а второй 2, и если там будут режки, то они выиграли?

Да, на оба вопроса

Мы говорим про ориентированный на чтение?

аффтар вообще ни о чем не говорил. он говорит, типа, что хочет крутой реализации, на любые уточняющие вопросы плюется и топает ногами.

Т.е. один может сказать 1, а второй 2, и если там будут режки, то они выиграли?

режек там точно не будет… потому что есть только решки. :)))

Да все что угодно лучше спинлока в кеше, ну лол же. Чтение блокируется записью и латентность летит к чертям.

Реальный вопрос: «ты глотаешь или сплёвываешь?».

Долго думал (не справился бы за короткий срок), вроде так надо рассуждать:

1. Мы пытаемся оптимизировать худший случай, значит, число бросков первого и второго шара примерно равны, если точнее, то их сумма в худшем случае всегда константа.
2. Первым шариком мы примерно определяем место, откуда кидать, вторым учтоняем
3. Кинув шарик 1 с этажа X, у нас осталось проверить X-1 этажей вторым шариком, таким образом, число бросков составит X-1+1(бросок первого шарика)=X, если первый шарик разбился, т.е. в худшем случае
4. Следующий раз мы будем кидать шарик с этажа (X-1)+X, а число бросков второго шарика сократится до X-2…
5. Продолжим процесс до достижения сотого этажа, очевидно, что уменьшающиеся шаги первого шарика конечны (X<100) и уменьшаются. Запишем формулу:
   X+(X-1)+(X-2)+...+1=100
6. Заметим, что у нас арифметическая прогрессия… Вспомним сумму членов арифметической прогрессии и получим формулу
   X*(X+1)/2=100
7. Решим формулу: X^2+X=200 X^2+X-200=0 D=b^2-4ac=1+800=801 sqrt(D)=28.3(с какими-то там копейками) x1=(-1-sqrt(D))/(2*1)<0, отбрасываем нафиг x2=(-1+sqrt(D))/(2*1)=27.3/2=13.65, округляем, 14
8. Записываем этажи с которого бросать первый шарик:
   14, 14+13=27, 27+12=39, 39+11=50, 50+10=60, 60+9=69, 69+8=77, 77+7=84 84+6=90 90+5=95 95+4=99
   Вторым шариком уточняем этаж (от предыдущей попытке вверх, пока не разобьётся), если первый разбивается, сумма бросков не превысит 14, задача решена.

Товарищ — лживый баран. Вопрос был не про самый быстрый кеш. Вопрос вообще был открытым, нужно было порассуждать и предложить что-то лучше банальной мапы под спинлоком.

Большинство

Чтение блокируется записью и латентность летит к чертям.

в данном случае спинлок на ЭЛЕМЕНТЕ кеша. то есть конкуренция будет только если другой тред влез именно на данный вход хештаблицы, коих много…а чтение неминуемо будет блокироваться записью, если конечно не применять rcu, но тут тоже вопрос - а сколько это rcu стоит в данном случае. Может проще заблокировать тред, поменять данные, и разблокировать, чем делать копию. это вопрос сложный.

Вопрос вообще был открытым, нужно было порассуждать и предложить что-то лучше банальной мапы под спинлоком.

ну так ждем правильный ответ… кстати «банальная мапа под спинлоком» в 90 процентов случаев будет еще и похуже «банальной мапы под банальным мьютексом», если там нет полной свалки тредов на хеше. спинлок имеет смысл если треды ломятся на этот несчастный кеш, и друг другу мешают столь активно, что временные затраты вставания на мьютекс становится значительными по сранению со времением остальных деяний. тогда можно и на спинок вставать. это проблему решит не очень(все равно будут толкаться), но часть времени освободится.

Ответ был, я ссылку давал. Проспись, болезный, а то тебе совсем плохо.

Тебе сказал нет, ибо задачки на собеседовани не решаются через «импорт збс»

А там и не надо ничего импортировать, это встроенные средства Clojure. Immutable persistent map внутри атома.

Атом может содержать значение (например, immutable persistent map) и атомарно заменять одно значение на другое. Останется только набыдлокодить несколько функций для поиска в кэше, помещения значения в кэш и удаления значения из кэша. Дрочить вручную мьютексы не нужно.

Если же хочется импорт збс, то можно почитать сюда.

в данном случае спинлок на ЭЛЕМЕНТЕ кеша.

Ты ЭЛЕМЕНТ кеша не собираешься обновлять? :)

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

RCU в любом случае дешевле.

Может проще заблокировать тред, поменять данные, и разблокировать, чем делать копию. это вопрос сложный.

Нет, это очень простой вопрос. Если у тебя многопоточное чтение динамически аллоцируемых объектов, то быстрее RCU. Если у тебя многопоточное чтение чего-то, что влезает в машинное слово, то тебе достаточно аналогов READ_ONCE()/WRITE_ONCE(). spinlock при многопоточном чтении будет хуже в любом случае.

P.S. Я, кстати, не очень понимаю, причем тут размер хештаблицы. Если у тебя десять тысяч элементов, 64 треда, и все 64 треда решили получить ключик 0x1234, то они все припрутся в одну и ту же ячейку.

Использование языка со встроенными средствами для синхронизации — это частный случай импорта збс.

Использование языка со встроенными средствами для синхронизации — это частный случай импорта збс.

Вы нанимаете людей работу делать или мьютексы дрочить?

Так модно потому что.

Ну нет. Если серьёзно 3 причины есть. Из-за двух из них альтернатива, которую позволяет первая не прижилась

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

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

Нет, это очень простой вопрос. Если у тебя многопоточное чтение динамически аллоцируемых объектов, то быстрее RCU.

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

Какие ещё причины кроме того, что диск не может провалиться в круглую дыру меньшего диаметра?

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

Ты RCU только на картинках видел?

для кеша кстати вариант один писатель - много читателей вряд ли подходит. там писателей много.

Это зависит от архитектуры.

Как бы вы написали свой ассоциативный массив?

Даже не пытался бы.

Такой вариант подходит?

Я ответил ''не знаю''. Подошло. А так это для было плюсцов, потом действительно std::unordered_map заменяли с профитом на кастомные хэш-таблицы в горячих местах. Сами правда не писали, так как выбора хватало.

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

Если по возможности избегает ручной синхронизации – значит, шарит? %)

Просто делать, как и круглые коллекторы, можно перекатывать. А так, можно было делать и в форме треугольника рёло, тоже не провалится никогда. Ну и лазить, не зацепишься.

P.S. Я, кстати, не очень понимаю, причем тут размер хештаблицы. Если у тебя десять тысяч элементов, 64 треда, и все 64 треда решили получить ключик 0x1234, то они все припрутся в одну и ту же ячейку.

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

если припрутся, на чтение - то пофиг.

Я так понимаю, спинлоки ты тоже только на картинке видел?

если на запись, то будут блокировки.

Они и на чтение будут, в твоем сценарии :)

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

Это если у тебя chaining. В этот же момент встают и все желающие прочитать :)

Друг с другом математики никак взаимодействовать не смогут

Какую стратегию им выбрать?

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

Ты RCU только на картинках видел?

я даже в картинках не видел :))) не то что в реальной жизни. там еще складно работает если писатель один читателей много. но если писателей много…оно вообще работает?

Да, явно чего-то не хватает. С такими вводными это выглядит невозможным.

Это если у тебя chaining. В этот же момент встают и все желающие прочитать :)

тут есть такое простое соображение, почему предоставлять безнаказанно читать кому-то устаревший мусор, безо всякого ожидания - это идиотизм… потому что это УСТАРЕВШИЙ мусор и он уже не актуален. и все что ты сделаешь, пусть даже не встав в ожидание, с этим УСТАРЕВШИМ мусором - уже не актуально, и ты зря суетился. тебе немедля придется переделать всю работу на новых данных.

я даже в картинках не видел :))) не то что в реальной жизни. там еще складно работает если писатель один читателей много. но если писателей много…оно вообще работает?

Конечно нет, оно в этом случает вызывает десант динозавров из космоса, которые съедают автора.

тут есть такое простое соображение, почему предоставлять безнаказанно читать кому-то устаревший мусор, безо всякого ожидания - это идиотизм… потому что это УСТАРЕВШИЙ мусор и он уже не актуален. и все что ты сделаешь, пусть даже не встав в ожидание, с этим УСТАРЕВШИМ мусором - уже не актуально, и ты зря суетился. тебе немедля придется переделать всю работу на новых данных.

Я сперва подумал, что ты про когерентность, а ты просто бред пишешь. Данные, полученные из кеша, считаются устаревшими сразу же после получения :)

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

Ох уж эти сеньоры с их высокомерием.

Это зависит от свойств кеша.

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

Если бы они могли взаимодействовать (слышать друг друга), решение, конечно, было бы слишком простым. Число ведь можно какое угодно назвать - а в большом числе хоть «Войну и Мир» можно закодировать.
Но нет, слышать и вообще взаимодействовать они не могут.
Конечно, кажется, что решения нет. И я мог бы это даже обосновать (что, мол, решения нету), только вот парадокс - решение есть.