phantom-84 писал(а):
Как видно, получился сложный алгоритм. Думаю, многопоточный мог быть и проще. Когда в твоем алгоритме происходит ожидание (отдается управление стороннему потоку), в многопоточном может выполняться один из используемых потоков, т.е. общее время работы тоже будет уменьшаться.
Оба содержащихся здесь утверждения неверны. Начну с конца, поскольку там проще :)
Цитата:
Когда в твоем алгоритме происходит ожидание (отдается управление стороннему потоку), в многопоточном может выполняться один из используемых потоков, т.е. общее время работы тоже будет уменьшаться.
В моём алгоритме ожидание происходит только в случае, если не были вовремя прочитаны исходные данные или записаны выходные. И в том, и в другом случае многопоточность ровным счётом ничего не даёт, поскольку она также завязана на ввод-вывод: если данные ещё не поступили, то и обрабатывать нечего, а если поступили, но не завершена запись предыдущих результатов, то обрабатывать опять-таки нельзя, поскольку некуда помещать данные.
Цитата:
Думаю, многопоточный мог быть и проще.
Многопоточный алгоритм имеет целый ряд дополнительных сложностей, которые необходимо учитывать.
Во-первых, нужно заранее разбить работу на несколько потоков, т.е. каким-то образом определить принцип разделения ещё не прочитанных входных данных на несколько порций, каждая из которых должна обрабатываться независимо от других. В некоторых случаях это сделать просто, в других же -- совершенно невозможно (например, когда обработка последующих данных каким-то образом связана с обработкой предыдущих). Таким образом, многопоточность не всегда позволит повысить производительность, если доступен лишь синхронный ввод-вывод, в то время как предложенный мною однопоточный алгоритм будет работоспособен всегда, ведь собственно обработка данных там ведётся строго последовательно.
Во-вторых, слишком большое количество потоков может быть вообще недопустимым либо же вызывать слишком большие накладные расходы (например, попробуй перекодируй файл размером 1 Гбайт, если перекодировка ведётся порциями по 1 Кбайту -- запустить сразу миллион потоков вряд ли какая система позволит). Значит, в общем случае надо предусматривать логику для того, чтобы обходиться сравнительно малым числом потоков, постоянно "подкармливая" их новой работой. Это, в свою очередь, требует учёта уже проделанной работы и планирования дальнейшей, что вряд ли будет совсем уж элементарно (и уж точно не будет проще моего алгоритма, где, собственно говоря, выполняется линейная последовательность простых операций).
В-третьих, многопоточная обработка подразумевает некоторую "хаотичность" в выполнении операций, что не всегда допустимо или же нежелательно. Например, в общем случае файл лучше считывать и записывать строго последовательно от начала к концу, поскольку в этом случае ввод-вывод выполняется быстрее (исключаются ненужные перемещения головок, например). В других случаях ввод-вывод вообще может выполняться только строго последовательно. В таких ситуациях необходимо обеспечивать дополнительную синхронизацию операций ввода-вывода между собой, что порядком усложняет общую логику, ну а у меня это достигается совершенно естественным образом, поскольку ввод-вывод в моём случае выполняется тоже последовательно.
В-четвёртых, сама по себе многопоточность даже при соблюдении всех перечисленных выше условий отнюдь не гарантирует повышения производительности. Рассмотрим три случая.
а) "Чистое" время, требуемое для ввода-вывода, заведомо больше времени, потребного на обработку информации. В этом случае многопоточность, очевидно, не даёт абсолютно никакого выигрыша по сравнению с моим однопоточным алгоритмом: поскольку я запускаю одну за другой две операции чтения, а потом две операции записи, а обработка информации занимает заведомо меньше времени, чем связанный с этой обработкой ввод-вывод, я всегда буду успевать завершить обработку очередной порции и запустить следующую операцию ввода-вывода. В результате ввод-вывод будет работать непрерывно, а процессор -- только то время, которое нужно на обработку данных да запуск новых операций (последнее обычно существенно меньше времени обработки).
б) Время на ввод-вывод очень близко ко времени на обработку. Собственно, это один из граничных случаев для п. а). Поскольку обработка всё ещё выполняется достаточно быстро, простои ввода-вывода, если обработка очередной порции будет длиться дольше, чем подготовка данных для следующей, будут минимальными. Минимальными будут и простои процессора в случае неготовности данных. В целом это получается идеально сбалансированный вариант, где возможности и ввода-вывода, и процессора используются практически на 100%.
в) Время на ввод-вывод заведомо меньше времени обработки. В случае, если физически имеется лишь один процессор, т.е. если в каждый момент времени работать может лишь один поток, многопоточность никакого выигрыша не даёт. В моём алгоритме процессор, дождавшись первой порции данных (а её ждать придётся в любом случае), далее будет всегда загружен на все 100%, поскольку ввод-вывод последующих порций будет занимать заведомо меньше времени. В многопоточном же алгоритме по мере запуска новых операций ввода-вывода потребуется отсутствующее у меня переключение потоков. Хотя собственно переключение при условии использования одного и того же виртуального адресного пространства (исполнения всех потоков в рамках одной задачи) -- операция дешёвая и не отличается от перехода между потоком и ядром (а он всегда выполняется при запуске операций ввода-вывода), однако кэш в этом случае будет частично "сыпаться": данные, накопленные в нём одним потоком (по крайней мере, стек), будут вытесняться данными другого потока. В итоге в лучшем случае производительность моего однопоточного алгоритма и альтернативного многопоточного будет одинаковой, но, скорей всего, многопоточный окажется несколько медленнее. Замечу, что здесь считается, что собственно процессорное время в обоих алгоритмах затрачивается одинаковое, а ведь в многопоточном алгоритме, как я говорил выше, скорее всего, потребуются дополнительные действия для синхронизации потоков и разделения работы между ними. Таким образом, реальный выигрыш от многопоточности можно получить лишь в том случае, когда у нас одновременно выполняются два условия: время ввода-вывода меньше времени обработки и компьютер имеет несколько процессоров. Однако здесь мы приходим к...
В-пятых. Честно говоря, складывается впечатление, что Вы упорно игнорируете тот факт, что наличие асинхронного ввода-вывода совершенно не исключает использования его в синхронном режиме, что я уже неоднократно подчёркивал. В частности, ничто не мешает реализовать многопоточный ввод-вывод с асинхронным вводом-выводом, работающим как синхронный, -- в этом случае получим тот же самый результат, как если бы ОС обеспечивала только и исключительно синхронный ввод-вывод. Однако -- подчеркну ещё раз, -- наличие асинхронного ввода-вывода открывает перед программистом дополнительные возможности по повышению эффективности приложений, нисколько при этом не уменьшая возможностей использования синхронного ввода-вывода, в то время как наличие только синхронного начисто лишает программиста подобных возможностей.
Пы.Сы. Попробуйте достаточно подробно расписать многопоточный алгоритм для реализации подобной обработки данных с синхронным вводом-выводом примерно на том уровне, как расписал я (т.е. каждый пункт -- это либо некий системный вызов, либо логически законченная часть обработки внутри потока). Тогда и можно будет предметно сравнить, что проще.
Вход
Регистрация
FAQ
Поиск
