Ах да, в Яндексе, вроде, спрашивают при поступлении на работу популярный вопрос "нужно отобразить последние N линий у K-гигабайтного файла. как бы вы это реализовывали?"
идем на конец, отматываем 2 Мб (это эмпирическая цифра, тащемта, достаточно запустить какой-нибудь dd на данном винте с разными скоростями, чтобы вывести ее), парсим, ищем \n, если нет, то еще на 2 Мб назад и читаем. Что сложного ?
при dd ты делаешь последовательное чтение. ну и вообще способ говно, проще реализовать уже конечную программу и померять на разных объемах. но тогда метод по сути твой получается "ну попробовать разное, хуле".
я говорю о том, что даже если взять блок равным кешу винчестера — если ты задом наперед будешь блоками читать — скорость может быть не равной той, если будешь в нормальном порядке читать.
Потери на передвижение будут, конечно. Но они принебрежительно малы, если читать Мегабайтами, да еще и по размеру кэша винчестера. Здесь еще рано говорить о том, что будет полноценный рандом акцесс (по качественным характеристикам).
ок. допустим кеш 1 Мб. если я попрошу прочитать 10 Мб — что произойдёт? чем это хуже того, что я 10 раз попрошу 1 Мб? всё равно ведь просто операционная система вместо меня 10 раз попросит по 1 Мб, или я неправ?
ну как это не выиграешь, операционка не будет туда сюда к твоему коду и обратно дёргаться, ну и одним куском выделит 10 Мб. ну и + я не уверен, что не выиграю в скорости.
короче я тут не знаток вообще ни разу (потому как "правильный" ответ не знаю), но вот блять как объяснить/доказать, что ты выиграешь или не выиграешь.
ну или в другую сторону: если выделять по 100Кб а не 1 Мб — почему ты проиграешь? почему именно размером буфера мерять, а не меньше?
Мда, питониста(джависта?) сразу видно. Память налево, память направо.
>>ну как это не выиграешь, операционка не будет туда сюда к твоему коду и обратно дёргаться, ну и одним куском выделит 10 Мб.
К какому коду дергаться ? Системный вызов read ? Да, дорого, но опять же меркнет по сравнению с самим IO. Зачем ты собираешься выделять тонны памяти, если первые 4 строки могут лежать в первом метре, кхм ?
>>ну или в другую сторону: если выделять по 100Кб а не 1 Мб — почему ты проиграешь? почему именно размером буфера мерять, а не меньше?
Синхронизация с кэшем тоже операция, если мы о ней вспомним. Отложенный или прямой он — не важно. Вот и получается, что чем лучше данные попадают в кэш, тем меньше удельный телодвижений на эффективность.
Например, когда речь идет о перемножении матриц, скорость (FLOPS) резко взлетает, если ты делаешь блочное умножение, а блок ложится в L2 кэш.
> Мда, питониста(джависта?) сразу видно. Память налево, память направо.
Нет, ну я понимаю, что ты прав, но моей матчасти действительно не хватает чтоб ответить точно на все вопросы. И дебильные предложения (уменьшить или увеличить блок) задаю чисто чтоб послушать твоё объяснение, "почему именно" ) Разобраться, естественно, самому в будущем тоже придется и надо будет.
> Синхронизация с кэшем тоже операция, если мы о ней вспомним. Отложенный или прямой он — не важно. Вот и получается, что чем лучше данные попадают в кэш, тем меньше удельный телодвижений на эффективность.
Осталось только сравнить (если я правильно понимю) скорость чтения данных и стоимость синхронизации с кешем. К примеру, если скорость чтения крайне мала, то дороже будет "прочитать больше, пусть даже в кеш", чем "прочитать немного, поискать там, почитать еще". Хотя может я неправ и в жизни операция синхронизации дорогая сильно.
Ну, я вообще считаю что правильным ответом было бы выяснение до последнего данных о записях, потому что в реальной жизни таки можно предсказать длинны строк, или усреднить как-то.
Почему к концу ? Операционка транслирует твой запрос на сдвиг к драйверу контроллера же. Сдвиг может быть абсолютным и относительным. Как арифметика указателей же.
23 comments
recommend
bookmark
subscribe
tail -n N file.txt :)
а вообще, ежу понятно, что сикаешься на конец и отматываешь строки по \n
как, задом-наперед? каждый раз seek на символ меньше? если нет — то блоками какого размера? почему именно такого?
идем на конец, отматываем 2 Мб (это эмпирическая цифра, тащемта, достаточно запустить какой-нибудь dd на данном винте с разными скоростями, чтобы вывести ее), парсим, ищем \n, если нет, то еще на 2 Мб назад и читаем. Что сложного ?
ооо. а вот про dd и эмпирическую цифру, пожалуйста, поподробнее. в этом вообще вся соль вопроса, в общем-то.
{
dd if=big_file of=/dev/null -bs=i
sleep (10) // seconds
kill -USR1 `pidof dd`
}
i от 256k до 64MB где-то.
Если без предварительных тестов, то я бы привязался к объему кэша винчестера * кол-во участников в RAID (если они есть)
при dd ты делаешь последовательное чтение. ну и вообще способ говно, проще реализовать уже конечную программу и померять на разных объемах. но тогда метод по сути твой получается "ну попробовать разное, хуле".
Ок, Лев Толстой.
Прочитай последнее мое замечание, например, про кэш винчестера.
>> проще реализовать уже конечную программу и померять на разных объемах
Это вообще всегда верно. Оптимизация по факту.
>>при dd ты делаешь последовательное чтение.
Да, а чем это мешает ?
>>метод по сути твой получается "ну попробовать разное, хуле".
Посмотри, как GParted перемещает разделы и УДИВИСЬ.
я говорю о том, что даже если взять блок равным кешу винчестера — если ты задом наперед будешь блоками читать — скорость может быть не равной той, если будешь в нормальном порядке читать.
или ты говоришь, что будет равной?
Потери на передвижение будут, конечно. Но они принебрежительно малы, если читать Мегабайтами, да еще и по размеру кэша винчестера. Здесь еще рано говорить о том, что будет полноценный рандом акцесс (по качественным характеристикам).
ок. допустим кеш 1 Мб. если я попрошу прочитать 10 Мб — что произойдёт? чем это хуже того, что я 10 раз попрошу 1 Мб? всё равно ведь просто операционная система вместо меня 10 раз попросит по 1 Мб, или я неправ?
Ты не выиграешь в скорости, а операционка сделает allocate в 10 Мб, а не в 1. Ебаный пиздец же.
ну как это не выиграешь, операционка не будет туда сюда к твоему коду и обратно дёргаться, ну и одним куском выделит 10 Мб. ну и + я не уверен, что не выиграю в скорости.
короче я тут не знаток вообще ни разу (потому как "правильный" ответ не знаю), но вот блять как объяснить/доказать, что ты выиграешь или не выиграешь.
ну или в другую сторону: если выделять по 100Кб а не 1 Мб — почему ты проиграешь? почему именно размером буфера мерять, а не меньше?
Мда, питониста(джависта?) сразу видно. Память налево, память направо.
>>ну как это не выиграешь, операционка не будет туда сюда к твоему коду и обратно дёргаться, ну и одним куском выделит 10 Мб.
К какому коду дергаться ? Системный вызов read ? Да, дорого, но опять же меркнет по сравнению с самим IO. Зачем ты собираешься выделять тонны памяти, если первые 4 строки могут лежать в первом метре, кхм ?
>>ну или в другую сторону: если выделять по 100Кб а не 1 Мб — почему ты проиграешь? почему именно размером буфера мерять, а не меньше?
Синхронизация с кэшем тоже операция, если мы о ней вспомним. Отложенный или прямой он — не важно. Вот и получается, что чем лучше данные попадают в кэш, тем меньше удельный телодвижений на эффективность.
Например, когда речь идет о перемножении матриц, скорость (FLOPS) резко взлетает, если ты делаешь блочное умножение, а блок ложится в L2 кэш.
> Мда, питониста(джависта?) сразу видно. Память налево, память направо.
Нет, ну я понимаю, что ты прав, но моей матчасти действительно не хватает чтоб ответить точно на все вопросы. И дебильные предложения (уменьшить или увеличить блок) задаю чисто чтоб послушать твоё объяснение, "почему именно" ) Разобраться, естественно, самому в будущем тоже придется и надо будет.
> Синхронизация с кэшем тоже операция, если мы о ней вспомним. Отложенный или прямой он — не важно. Вот и получается, что чем лучше данные попадают в кэш, тем меньше удельный телодвижений на эффективность.
Осталось только сравнить (если я правильно понимю) скорость чтения данных и стоимость синхронизации с кешем. К примеру, если скорость чтения крайне мала, то дороже будет "прочитать больше, пусть даже в кеш", чем "прочитать немного, поискать там, почитать еще". Хотя может я неправ и в жизни операция синхронизации дорогая сильно.
Надо проверять, конечно.
Я все-таки убежден, что на такие вопросы надо отвечать методиками а не цифрами :) Или я не прав ? :)
Я откуда знаю :-)
Ну, я вообще считаю что правильным ответом было бы выяснение до последнего данных о записях, потому что в реальной жизни таки можно предсказать длинны строк, или усреднить как-то.
Хм, я тоже об этом думал (вести какую-то статистику).
ну, собственно еще остаётся большой вопрос: как операционная система реализует seek? она каждый раз фигачит к концу файла или где?
Почему к концу ? Операционка транслирует твой запрос на сдвиг к драйверу контроллера же. Сдвиг может быть абсолютным и относительным. Как арифметика указателей же.
типа в драйвере запоминается куда был seek, и в операционке запоминается? и потом относительный сдвиг высчитывается?
По идее, это так в неизменном виде и должно отдаваться контроллеру. Хотя тут уже точно не знаю, но это мелочи. Адресная арифметика, повторюсь.
Вот, посмотри видео от начала до конца, тебе станет ясно, рли.
класс! я как раз первый раз подошел к компьютеру!