FIFO или LIFO?
{для непрограммистов:
FIFO: First In - First Out, первый пришёл - первый пошёл;
LIFO: Last In - First Out, последний пришёл - первый пошёл}
Началась эта история как обсуждение того, в каком порядке сервер должен обслуживать запросы и я услышал мысль о том, что есть смысл делать это не в том порядке, в котором они приходят, а в обратном.
Сначала я это воспринял как шутку, но после того, как понял, что это всерьёз, эта мысль меня больше не отпускает и я даже начинаю использовать обратный порядок для своих личных дел.
Изначально парадокс состоит в том, что FIFO выглядит "естественно" и даже "честно".
Тот, кто пришёл раньше, уже ждёт дольше, его надо бы обслужить, а тот, кто только что пришёл, не так уж сильно обидится, если подождёт ещё немного.
В чём же выгода LIFO при обработке запросов или обычных своих дел?
Тут надо рассмотреть несколько факторов из реальной жизни.
1. Разница в этих алгоритмах начинает проявляться только тогда, когда дел в очереди накапливается больше одного, т.е. когда мы (или сервер) не успеваем обрабатывать дела по мере их поступления. Пока мы делаем одно, в очереди уже накопилось ещё несколько.
Поэтому сразу будем рассматривать случаи, когда очередь дел у нас не пустая.
2. [Почти] У каждого дела есть дэдлайн, время, до которого оно должно быть сделано, а после оно уже не имеет смысла (но может превратиться в одно или несколько других дел).
Поэтому если у нас поток запросов - такой большой, что мы заведомо с ними не справляемся, то нам так или иначе ПРИДЁТСЯ оставлять какие-то дела несделанными.
Тут уже наступает ощутимая разница между FIFO и LIFO: доля несделанных дел будет ровно такая же, зато вот время на выполнение дел, которые будут сделаны, будет значительно лучше! Ведь мы выполняем дела, которые только что поступили в список. А до тех, которые там лежат давно, уже менее вероятно, что вообще дойдёт.
Но если дело всё равно не будет сделано, то для результата нет и никакой разницы, в каком именно месте этого списка оно пролежало: в начале или в конце.
3. Представим, что режим работы у нас - "всплесками": мы в короткий промежуток времени получаем пачку заданий и потом у нас - тишина и времени достаточно на выполнение всего.
В этом случае мы будем успевать и в режиме FIFO и в режиме LIFO, при этом СРЕДНЕЕ время выполнения заданий будет ровно одинаковым. Просто FIFO выполнит все задания в прямом порядке, LIFO - в обратном.
Иногда этот нюанс бывает важным, если задания между собой как-то связаны, но если они независимы, но это всё равно.
При небольшом интервале между заданиями в пакете, у FIFO будет меньше разброс во времени выполнения задачи с момента попадания в очередь; у LIFO разброс будет больше, но лучше будет минимальное время, за которое удалось справиться.
Иногда минимальное время важно для отчётности.
Что мы имеем в результате?
* При небольших нагрузках разницы нет
* При средних нагрузках минимальное время лучше - у LIFO, максимальное - у FIFO, среднее - равно.
* При высоких нагрузках однозначно выигрывает ... (тадааам!) LIFO!
Неожиданно, да?
Выполнение заданий задом на перёд улучшает вашу производительность!
Кроме этого, для обычных человеческих дел тут ещё начинает играть роль психологический фактор: дело иногда откладывается и попадает в очередь по причине того, что его почему-то делать не хочется, не удобно, тяжело, [подберите отмазку].
И если человек для себя руководствуется принципом FIFO, то эти "неприятные" дела могут тормозить выполнение чего-то действительно простого - просто потому, что простые дела в списке идут "после".
В случае же LIFO просмотр дел всегда начинается с новых дел и у них всегда есть шанс быть сделанными прямо сейчас!
Со времени этого открытия для меня прошёл почти год, но до меня всё продолжают доходить новые и новые замечательные свойства этого подхода.
Интересно было бы обсудить.
FIFO: First In - First Out, первый пришёл - первый пошёл;
LIFO: Last In - First Out, последний пришёл - первый пошёл}
Началась эта история как обсуждение того, в каком порядке сервер должен обслуживать запросы и я услышал мысль о том, что есть смысл делать это не в том порядке, в котором они приходят, а в обратном.
Сначала я это воспринял как шутку, но после того, как понял, что это всерьёз, эта мысль меня больше не отпускает и я даже начинаю использовать обратный порядок для своих личных дел.
Изначально парадокс состоит в том, что FIFO выглядит "естественно" и даже "честно".
Тот, кто пришёл раньше, уже ждёт дольше, его надо бы обслужить, а тот, кто только что пришёл, не так уж сильно обидится, если подождёт ещё немного.
В чём же выгода LIFO при обработке запросов или обычных своих дел?
Тут надо рассмотреть несколько факторов из реальной жизни.
1. Разница в этих алгоритмах начинает проявляться только тогда, когда дел в очереди накапливается больше одного, т.е. когда мы (или сервер) не успеваем обрабатывать дела по мере их поступления. Пока мы делаем одно, в очереди уже накопилось ещё несколько.
Поэтому сразу будем рассматривать случаи, когда очередь дел у нас не пустая.
2. [Почти] У каждого дела есть дэдлайн, время, до которого оно должно быть сделано, а после оно уже не имеет смысла (но может превратиться в одно или несколько других дел).
Поэтому если у нас поток запросов - такой большой, что мы заведомо с ними не справляемся, то нам так или иначе ПРИДЁТСЯ оставлять какие-то дела несделанными.
Тут уже наступает ощутимая разница между FIFO и LIFO: доля несделанных дел будет ровно такая же, зато вот время на выполнение дел, которые будут сделаны, будет значительно лучше! Ведь мы выполняем дела, которые только что поступили в список. А до тех, которые там лежат давно, уже менее вероятно, что вообще дойдёт.
Но если дело всё равно не будет сделано, то для результата нет и никакой разницы, в каком именно месте этого списка оно пролежало: в начале или в конце.
3. Представим, что режим работы у нас - "всплесками": мы в короткий промежуток времени получаем пачку заданий и потом у нас - тишина и времени достаточно на выполнение всего.
В этом случае мы будем успевать и в режиме FIFO и в режиме LIFO, при этом СРЕДНЕЕ время выполнения заданий будет ровно одинаковым. Просто FIFO выполнит все задания в прямом порядке, LIFO - в обратном.
Иногда этот нюанс бывает важным, если задания между собой как-то связаны, но если они независимы, но это всё равно.
При небольшом интервале между заданиями в пакете, у FIFO будет меньше разброс во времени выполнения задачи с момента попадания в очередь; у LIFO разброс будет больше, но лучше будет минимальное время, за которое удалось справиться.
Иногда минимальное время важно для отчётности.
Что мы имеем в результате?
* При небольших нагрузках разницы нет
* При средних нагрузках минимальное время лучше - у LIFO, максимальное - у FIFO, среднее - равно.
* При высоких нагрузках однозначно выигрывает ... (тадааам!) LIFO!
Неожиданно, да?
Выполнение заданий задом на перёд улучшает вашу производительность!
Кроме этого, для обычных человеческих дел тут ещё начинает играть роль психологический фактор: дело иногда откладывается и попадает в очередь по причине того, что его почему-то делать не хочется, не удобно, тяжело, [подберите отмазку].
И если человек для себя руководствуется принципом FIFO, то эти "неприятные" дела могут тормозить выполнение чего-то действительно простого - просто потому, что простые дела в списке идут "после".
В случае же LIFO просмотр дел всегда начинается с новых дел и у них всегда есть шанс быть сделанными прямо сейчас!
Со времени этого открытия для меня прошёл почти год, но до меня всё продолжают доходить новые и новые замечательные свойства этого подхода.
Интересно было бы обсудить.