echo
, которая печатает строку в stdout, и есть true
, которая ничего не делает, а только завершается с нулевым кодом.Среди множества простых Unix-команд спряталась команда
yes
. Если запустить её без аргументов, то вы получите бесконечный поток символов "y", каждый с новой строки:y
y
y
y
(...ну вы поняли мысль)
Хотя на первый взгляд команда кажется бессмысленной, но иногда она бывает полезной:
yes | sh boring_installation.sh
Когда-нибудь устанавливали программу, которая требует ввести "y" и нажать Enter для установки? Команда
yes
приходит на помощь! Она аккуратно выполнит эту задачу, так что можете не отвлекаться от просмотра Pootie Tang.Пишем yes
Вот базовая версия на… хм… BASIC.
10 PRINT "y"
20 GOTO 10
А вот то же самое на Python:
while True:
print("y")
Кажется простым? Погодите!
Как выясняется, такая программа работает довольно медленно.
python yes.py | pv -r > /dev/null
[4.17MiB/s]
Сравните со встроенной версией на моём «маке»:
yes | pv -r > /dev/null
[34.2MiB/s]
Так что я попытался написать более быструю версию на Rust. Вот моя первая попытка:
use std::env;
fn main() {
let expletive = env::args().nth(1).unwrap_or("y".into());
loop {
println!("{}", expletive);
}
}
Некоторые пояснения:
- Строка, которую мы печатаем в цикле, — это первый параметр командной строки под названием expletive. Это слово я узнал из руководства
yes
. - Я использую
unwrap_or
, чтобы получить expletive из параметров. Если параметры не установлены, по умолчанию используется "y". - Параметр по умолчанию конвертируется из строкового фрагмента (
&str
) вowned()
в куче (String
) при помощиinto()
.
Протестируем.
cargo run --release | pv -r > /dev/null
Compiling yes v0.1.0
Finished release [optimized] target(s) in 1.0 secs
Running `target/release/yes`
[2.35MiB/s]
Упс, ничего особенно не улучшилось. Она даже медленнее, чем версия на Python! Это меня заинтересовало, так что я поискал исходники реализации на C.
Вот самая первая версия программы, которая вышла в составе Version 7 Unix за почётным авторством Кена Томпсона 10 января 1979 года:
main(argc, argv)
char **argv;
{
for (;;)
printf("%s\n", argc>1? argv[1]: "y");
}
Никакой магии.
Сравним со 128-строчной версией из комплекта GNU coreutils, зеркало которого есть на Github. После 25 лет программа всё ещё в активной разработке! Последнее изменение кода произошло около года назад. Она довольно быстрая:
# brew install coreutils
gyes | pv -r > /dev/null
[854MiB/s]
Важная часть находится в конце:
/* Repeatedly output the buffer until there is a write error; then fail. */
while (full_write (STDOUT_FILENO, buf, bufused) == bufused)
continue;
Ага! Так здесь просто используется буфер для ускорения операций записи. Размер буфера устанавливается постоянной
BUFSIZ
, которая выбирается для каждой системы, чтобы максимально оптимизировать операции ввода-вывода (см. здесь). На моей системе она была установлена как 1024 байта. В реальности лучшая производительность оказалась при 8192 байтах.Я расширил свою программу Rust:
use std::io::{self, Write};
const BUFSIZE: usize = 8192;
fn main() {
let expletive = env::args().nth(1).unwrap_or("y".into());
let mut writer = BufWriter::with_capacity(BUFSIZE, io::stdout());
loop {
writeln!(writer, "{}", expletive).unwrap();
}
}
Здесь важно, чтобы размер буфера делился на четыре, это гарантирует выравнивание в памяти.
Такая программа выдаёт 51,3 МиБ/с. Быстрее, чем версия, установленная в моей системе, но намного медленнее чем вариант от автора найденного мной поста на Reddit. Он говорит, что добился скорости 10,2 ГиБ/с.
Дополнение
Как обычно, сообщество Rust не подкачало. Как только эта статья попала в подреддит о Rust, пользователь nwydo указал на предыдущее обсуждение этой темы. Вот их оптимизированный код, который пробивает 3 ГБ/с на моей машине:
use std::env;
use std::io::{self, Write};
use std::process;
use std::borrow::Cow;
use std::ffi::OsString;
pub const BUFFER_CAPACITY: usize = 64 * 1024;
pub fn to_bytes(os_str: OsString) -> Vec<u8> {
use std::os::unix::ffi::OsStringExt;
os_str.into_vec()
}
fn fill_up_buffer<'a>(buffer: &'a mut [u8], output: &'a [u8]) -> &'a [u8] {
if output.len() > buffer.len() / 2 {
return output;
}
let mut buffer_size = output.len();
buffer[..buffer_size].clone_from_slice(output);
while buffer_size < buffer.len() / 2 {
let (left, right) = buffer.split_at_mut(buffer_size);
right[..buffer_size].clone_from_slice(left);
buffer_size *= 2;
}
&buffer[..buffer_size]
}
fn write(output: &[u8]) {
let stdout = io::stdout();
let mut locked = stdout.lock();
let mut buffer = [0u8; BUFFER_CAPACITY];
let filled = fill_up_buffer(&mut buffer, output);
while locked.write_all(filled).is_ok() {}
}
fn main() {
write(&env::args_os().nth(1).map(to_bytes).map_or(
Cow::Borrowed(
&b"y\n"[..],
),
|mut arg| {
arg.push(b'\n');
Cow::Owned(arg)
},
));
process::exit(1);
}
Так это же совсем другое дело!
- Мы подготовили заполненный строковый буфер, который будет заново использоваться в каждом цикле.
- Поток стандартного вывода (stdout) защищён блокировкой. Так что вместо непрерывного захвата и освобождения мы держим его всё время.
- Используем нативные для платформы
std::ffi::OsString
иstd::borrow::Cow
, чтобы избежать ненужных размещений в памяти.
Единственное, что я могу добавить, так это
убрать необязательный mut
. Извлечённые уроки
Тривиальная программа
yes
на самом деле оказалась не такой простой. Для улучшения производительности в ней используется буферизация вывода и выравнивание памяти. Переработка стандартных инструментов Unix — увлекательное занятие и оно заставляет ценить те изящные трюки, которые делают наши компьютеры быстрыми.
Комментарии (49)
Color
09.11.2017 12:35Переработка стандартных инструментов Unix — увлекательное занятие и оно заставляет ценить те изящные трюки, которые делают наши компьютеры быстрыми
Теперь буду говорить на кодревью: "Это не костыль, это изящный трюк!"
mrsantak
09.11.2017 13:09+1Оптимизации для Бога Оптимизации! Производительности для Трона Производительности!
windgrace
09.11.2017 13:17На удивление, наивная реализация (и скомпилированная безо всяких оптимизаций) на Хаскелле выдаёт 158MiB/s на рабочем десктопе:
module Main where main :: IO () main = do putStrLn yes yes :: String yes = 'y' : '\n' : yes
Правда, встроенная `yes` показывает 3.8GiB/s, но это мелочи жизни=)WRONGWAY4YOU
09.11.2017 17:07Твоя программа не реализовывает спецификацию утилиты
yes
. В статье написано ведь, что утилита должна принимать аргумент коммандной строки, заменяющий"y"
в случае наличия.windgrace
09.11.2017 17:33Я вдохновлялся, скорее, наивными реализациями
yes
из начала статьи, они тоже не умеют принимать аргументы из командной строки. В любом случае, версия, которая это умеет, ничем по скорости не отличается:
module Main where import Data.Function (fix) import System.Environment (getArgs) main :: IO () main = do args <- getArgs let str = if null args then "y" else head args putStr $ fix $ \s -> str ++ "\n" ++ s
Cheater
09.11.2017 13:23+1Там в комментах на reddit народ взялся оптимизировать ту часть, что стоит за фильтром (| pv), и добился уже ~123 Гб/сек :)
www.reddit.com/r/unix/comments/6gxduc/how_is_gnu_yes_so_fast/diua761Akon32
09.11.2017 15:13Разве для этого не нужен как минимум ~120GHz CPU?
Cheater
09.11.2017 15:23Нет, здесь ограничением является частота DRAM, а не CPU.
en.wikipedia.org/wiki/Memory_bandwidth#Bandwidth_computation_and_nomenclature
dmrt
09.11.2017 14:12yes | sh boring_installation.sh
А почему тут yes прекращает свой бесконечный цикл и передает управление следующему скрипту в конвейере?aragaer
09.11.2017 14:30+2Они работают «параллельно», а между ними пайп, имеющий ограниченную емкость. Как только пайп заполнен («следующий» скрипт не читает из него), yes будет просто блокироваться на операции записи.
dmrt
09.11.2017 14:41Ах вот как, они работают параллельно сразу, спасибо!
Я всегда думал, что они работают последовательно, сначала первая команда запустится и завершится, запишет выходные данные, затем вторая запустится и прочитает входные данные.khim
09.11.2017 23:02Я всегда думал, что они работают последовательно, сначала первая команда запустится и завершится, запишет выходные данные, затем вторая запустится и прочитает входные данные.
Дык эта. Времена MS DOS давно прошли…
varnav
09.11.2017 16:11Впечатляющее количество строк у оптимизированной Rust версии для столь простой задачи.
agmt
09.11.2017 17:11Надо взять язык с большим количеством абстракций, чтобы героически разгребать их и достукиваться до нативных объектов.
Немного странный пост: всем и так понятно, что наиболее быстрым будет прямой вызов родных методов данной системы (и пачкой отправлять — тоже), что наиболее изящно выглядят на C.
numas
11.11.2017 19:25Хватило бы такого варианта, не понимаю, зачем они всё так усложнили.
use std::borrow::Cow; use std::io::{self, Write}; fn main() { const BUFFER_CAPACITY: usize = 32 * 1024; let expletive = std::env::args().nth(1) .map(|s| Cow::Owned(s + "\n")) .unwrap_or(Cow::Borrowed("y\n")); let buffer = expletive.repeat(BUFFER_CAPACITY / expletive.len()); let stdout = io::stdout(); let mut handle = stdout.lock(); loop { handle.write(buffer.as_bytes()).unwrap(); } }
К тому же, этот вариант, на моей машине, быстрее на 7% быстрее.
Disbeleiver
09.11.2017 17:17Ничего не понятно.
У меня при комбинации yes и pv, полученных из репы Ubuntu 16.04 и запущенных как есть,
yes | pv -r > /dev/null
на Lenovo T60 (дрова, ддр2 и T7200) = 1,92 GiB
на Dell M6700 (ddr3 и 3632QM) = 7.58 GiB
А автор до 3 ГБ/с c оптимизированным кодом м трудом добрался.
Что я делаю не так или что я не понял в задаче?windgrace
09.11.2017 17:37Есть подозрение, что всё очень сильно зависит от частоты памяти. Я скомпилировал свою наивную реализацию на разных машинах и получил разные (в разы, а то на порядки) результаты по скорости.
snp
09.11.2017 20:06Не всё так просто, по-моему. На 7-летней давности ноутбуке получаем 7GIB/s:
% yes |pv >/dev/null ^C.6GiB 0:00:05 [7.08GiB/s] [ <=> ]
Model name: Intel(R) Core(TM) i7-2640M CPU @ 2.80GHz L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 4096K
Linux 4.13.0-0.bpo.1-amd64
Type: DDR3 Speed: 1333 MHz
На достаточно новом сервере получаем 0.1GIB/s:
% yes |pv >/dev/null ^C76GiB 0:00:27 [ 108MiB/s] [ <=> ]
Model name: Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 25600K
Linux 4.4.79-1-pve
Type: DDR4 Speed: 2133 MHz
degs
09.11.2017 21:39Соль ситуации что yes вовсе не требуется быть быстрым, поскольку все клиенты запрашивающие подтверждение через stdin очевидно расчитаны на интерактивный ввод.
PlatinumThinker
10.11.2017 08:58есть реп со сборником реализаций данной команды на разных языках github.com/mubaris/yes
Shakhmin
10.11.2017 21:40Очень интересно описано, но поправьте меня, если не прав, pv считает, сколько через нее прошло (слово "прошло" — условно) за секунду. Если мы отправляем один символ "y", то это около одного символа, а если отправляем буфер, то это около 8k символов — разница почти на 4 порядка по pv скорее показывает, что оба примера работают с одинаковой скоростью в контексте "количества выданных y"
asmrnv777
10.11.2017 21:52Как выясняется, такая программа работает довольно медленно.
А на третьем питоне еще на 0.5 мб/с медленнее, чем на 2.7 :)
Oslegg
10.11.2017 22:00Стало интересно и решил посмотреть что-же получиться на Го.
Получилось так
package main import ( "bufio" "fmt" "os" ) var bufsize = 64 * 1024 func main() { y := byte('y') n := byte('\n') buf := make([]byte, 0x1000) fmt.Println(bufsize) for i := 0; i < len(buf)-2; i += 2 { fmt.Println(i) buf[i] = y buf[i+1] = n } f := bufio.NewWriterSize(os.Stdout, bufsize) defer f.Flush() for { f.Write(buf) } }
Результат:
$ ./yes| pv -r > /dev/null
[9.59GiB/s]
Системный yes выдаёт
$ yes | pv -r > /dev/null
[9.06GiB/s]
Oslegg
10.11.2017 22:31Пофикшенная версия с опциональным аргументом
package main import ( "bufio" "os" ) var bufsize = 64 * 1024 func main() { var y []byte // Get arg if len(os.Args) > 1 { y = []byte(os.Args[1] + "\n") } else { // Set output to y y = []byte("y\n") } yLen := len(y) // Create buffer buf := make([]byte, bufsize) // Popoulate buffer for i := 0; i < len(buf)-yLen; i += yLen { for s := 0; s < len(y); s++ { buf[i+s] = y[s] } } // Create buffered writer f := bufio.NewWriterSize(os.Stdout, bufsize) defer f.Flush() for { f.Write(buf) } }
скорость не поменялась (да и с чего-бы? :) )
youROCK
Ага, вот из-за наличия yes и приходится во всех критичных к вниманию юзера программах проверять на isatty(0) и читать прямо из /dev/pty вместо stdin :).
SirEdvin
Надеюсь, у вас же правда есть какой-то параметр
--force
в таком случае?youROCK
Смотря что за скрипт. У некоторых (у полу-одноразовых скриптов, которые действительно предполагается только руками запускать и никак иначе) такого флага нет и даже скрытой возможности запустить из скрипта тоже нет. Но обычно есть какой-то способ запустить её в батч-режиме, да. Иногда это что-то вроде значения типа "i_know_that_i_am_doing_very_bad_thing_and_i_read_documentation" в виде проверки md5(param) = "0d52fbfcafbb4f29983fff89e4184904", где само значение действительно зарыто в документации и его человек может найти, только прочитав документацию достаточно и поняв её.
AxisPod
Просить ввести рандомную строку из 10 символов.
mklochkov
Кажется, вы в одном шаге от изобретения
велосипедакапчи. Кстати, гугловая её реализация (та самая, где «поставьте галочку, если вы не робот») ни разу не тривиальна.bogolt
И анализировать их на этропию, если плохая — строка недостаточно рэндомная!
Akon32
это не так сложно:
askv
format C:? Yes! :)
Не очень понял, зачем этой программе такое мегабыстродействие?
Hvorovk
Ну логично же, если ооочень много yes поставить нужно, то такая программа, будет крайне мало времени отъедать, в отличии от реализации на питоне например.
alhimik45
Страшно представить программу которой требуется 3 гигабайта в секунду подтверждений и работает она быстрее чем получает эти подтверждения...
ainoneko
windgrace
Пара секунд — и ага…
4680864
У меня промелькнула мысль про какой-нибудь странный rm с рекурсивом но без форса, которому, при определённых обстоятельствах понадобилось бы очень-очень много раз жать y… Но, блин, 3 Гб? Даже отдалённо не получается придумать задачу ).