Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Почему компьютер выполняет 90% лишней работы ? / 25 сообщений из 55, страница 1 из 3
23.11.2009, 15:32:54
    #36326134
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
Если представить любую программу как граф пройденных состояний, то выяснится что 90% программа проходит по одним и тем же вершинам, получает одни и теже данные в каждом промежуточном узле. А что если снять данные в каждом узле вход/выход, детерменировать связи между функциями и не вызывать повторно на вычисление функции для которых заведомо известны результаты ?
...
Рейтинг: 0 / 0
23.11.2009, 15:43:24
    #36326171
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
вот открыл я опять вот эту страницу, а компьютер опять молотит один и тот-же html, тянет сначала его по сети и получает одни и теже данные. Хорошо что страница открывается довольно быстро, но реально открываться должна вообще моментально
...
Рейтинг: 0 / 0
23.11.2009, 15:47:47
    #36326191
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
301вот открыл я опять вот эту страницу, а компьютер опять молотит один и тот-же html, тянет сначала его по сети и получает одни и теже данные. Хорошо что страница открывается довольно быстро, но реально открываться должна вообще моментально
Чтобы она открывалась моментально, компьютер должен проанализировать все входящие в алгоритм её открытия шаги и доказать, что они все детерминированны. То что два раза подряд он проделал одинаковую работу при открытии этой страницы не означает, что всегда он будет проделывать одинаковую работу.

Далее результаты такого анализа должны быть сохранены.

Таким образом мы упираемся в 2 более страшные проблемы, нежели "второй раз обработать загрузку страницы". Компьютеру придется анализировать даже то, что мы, возможно, никогда в будущем повторно использовать не будем. И эти "анализы" придется сохранять - терабайтных винчестеров и гигагерцовых процессоров работать с этими массивами "анализов" быстро станет не хватать.
...
Рейтинг: 0 / 0
23.11.2009, 15:57:29
    #36326226
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
"зачем канализационные трубы делают такими толстыми? что бы они выдержали короткий пик нагрузок." (с)

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

4 8 15 16 23 42
...
Рейтинг: 0 / 0
23.11.2009, 16:01:27
    #36326241
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
301Если представить любую программу как граф пройденных состояний, то выяснится что 90% программа проходит по одним и тем же вершинам, получает одни и теже данные в каждом промежуточном узле. А что если снять данные в каждом узле вход/выход, детерменировать связи между функциями и не вызывать повторно на вычисление функции для которых заведомо известны результаты ?

Почитайте про функциональное программирование и кеширование вызовов функций.
...
Рейтинг: 0 / 0
23.11.2009, 16:46:56
    #36326435
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
an0nym
Чтобы она открывалась моментально, компьютер должен проанализировать все входящие в алгоритм её открытия шаги и доказать, что они все детерминированны.


Доказать это можно построив дерево связей.

an0nym
То что два раза подряд он проделал одинаковую работу при открытии этой страницы не означает, что всегда он будет проделывать одинаковую работу.


Согласен. Но в 90% случаев достаточно сделать небольшое сравнение закешированных входящих данных чтобы "отрезать" огромную ветку.

an0nym
Таким образом мы упираемся в 2 более страшные проблемы, нежели "второй раз обработать загрузку страницы". Компьютеру придется анализировать даже то, что мы, возможно, никогда в будущем повторно использовать не будем. И эти "анализы" придется сохранять - терабайтных винчестеров и гигагерцовых процессоров работать с этими массивами "анализов" быстро станет не хватать.

Терабайтов информации нет. Есть приложение, которое состоит обычно из 1-2 тыс. функций. Они образовуют огромных граф вызовов с вложенностью около 10. Целую огромную подветку можно отсечь в самом начале если закешировать вход/выход хотябы функций первых трех вложенностей.
Следвательно терабайтные данные могут свестись к табличке примерно на 2 тыс функции и типичных пару десятков вызовов для них.
...
Рейтинг: 0 / 0
23.11.2009, 16:48:57
    #36326441
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
zloy den301Если представить любую программу как граф пройденных состояний, то выяснится что 90% программа проходит по одним и тем же вершинам, получает одни и теже данные в каждом промежуточном узле. А что если снять данные в каждом узле вход/выход, детерменировать связи между функциями и не вызывать повторно на вычисление функции для которых заведомо известны результаты ?

Почитайте про функциональное программирование и кеширование вызовов функций.

Меня пока что интересует процедурное программирование и методы "над" оптимизаций.
...
Рейтинг: 0 / 0
23.11.2009, 17:56:05
    #36326644
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
301
Меня пока что интересует процедурное программирование и методы "над" оптимизаций.

С учетом того, что это машина состояний, то очень трудно хранить и кешировать вызовы каких-либо методов, т.к. они могут зависеть не только от параметров, но и от внутреннего состояния объектов или каких-то переменных. В функциональных языках (или хотя бы в программах, лишенных побочных эффектов) наиболее часто используемые функции можно кешировать без боязни что что-то будет упущено-такие функции всегда возвращают один и тот же результат для одинаковых параметров.
А как красиво сделать такое в программах, у методов которых есть побочные эффекты, я даже не представляю.
...
Рейтинг: 0 / 0
23.11.2009, 18:23:53
    #36326717
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
zloy den301
Меня пока что интересует процедурное программирование и методы "над" оптимизаций.

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

Можно распарсить тело метода и определить список переменных которые он может менять. Локальные и глобальные. Локальные переменные нас не интересуют. Глобальные переменные указывают связи между методами. Остается единственная проблема с внешними источниками данных. Таких как файловая система или база данных. Проблема появляется только для незамкнутой системы ( не идеальной ).
...
Рейтинг: 0 / 0
23.11.2009, 22:15:34
    #36327077
belugin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
это называется мемоизация
...
Рейтинг: 0 / 0
23.11.2009, 23:56:14
    #36327194
sqI
sqI
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
beluginэто называется мемоизация

спасибо за инфу. Речь именно о ней. Вот листаю гугл, но пока не могу найти пристойных примеров поддерживающих это "аппаратно", на уровне ОС или хотябы на уровне Виртуальной машины.
В основном речь идет о Сustom мемоизации на этапе разработки, что не позволяет автоматически ускорить работу уже созданного кода.
...
Рейтинг: 0 / 0
24.11.2009, 06:48:04
    #36327345
belugin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
sqI,
для этого надо, чтобы код был функционально чист
...
Рейтинг: 0 / 0
24.11.2009, 11:51:52
    #36327931
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
beluginsqI,
для этого надо, чтобы код был функционально чист

не обязательно. Достаточно построить дерево связей.
...
Рейтинг: 0 / 0
24.11.2009, 11:52:33
    #36327936
301
301
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
Для этого пришла мысль смотреть на алгоритм не как рукописную структуру, а с точки зрения рантайм прохождения данных
...
Рейтинг: 0 / 0
25.11.2009, 10:12:47
    #36330043
ALKIR
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
301... 90% программа проходит по одним и тем же вершинам...

"Чушь какая-то..."
Если вы строите конечный автомат – знаете все возможные комбинации параметров на входе и значений на выходе, тогда, казалось бы, куда проще создать карту соответствия. Однако размер такой карты соответствия, для, казалось бы, простого приложения может и будет занимать непозволительно много места (тривиальный пример – решение шахматной задачи). И, если учесть то, что современный компьютер под управлением современной операционной системы – это не одно приложение, а группа программ, которые "как-то" пытаются сосуществовать и делить ограниченные ресурсы (этого самого компьютера), то задача по определению такой карты соответствия для целого компьютера представляется не разрешимой...
Есть еще одно "но", как может показаться начинающему программисту: почему программы выполняют не оптимизированный код. Это происходит потому, что опытные программисты предпочитают использовать код повторно, и пусть этот код написан другими программистами, - главное, что он рабочий.
"Если работает – лучше не трогать..."
...
Рейтинг: 0 / 0
25.11.2009, 11:06:01
    #36330230
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
ALKIR301... 90% программа проходит по одним и тем же вершинам...

"Чушь какая-то..."
Если вы строите конечный автомат – знаете все возможные комбинации параметров на входе и значений на выходе, тогда, казалось бы, куда проще создать карту соответствия. Однако размер такой карты соответствия, для, казалось бы, простого приложения может и будет занимать непозволительно много места (тривиальный пример – решение шахматной задачи). И, если учесть то, что современный компьютер под управлением современной операционной системы – это не одно приложение, а группа программ, которые "как-то" пытаются сосуществовать и делить ограниченные ресурсы (этого самого компьютера), то задача по определению такой карты соответствия для целого компьютера представляется не разрешимой...
Есть еще одно "но", как может показаться начинающему программисту: почему программы выполняют не оптимизированный код. Это происходит потому, что опытные программисты предпочитают использовать код повторно, и пусть этот код написан другими программистами, - главное, что он рабочий.
"Если работает – лучше не трогать..."
+1.
...
Рейтинг: 0 / 0
25.11.2009, 13:00:18
    #36330643
sqI
sqI
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
ALKIR
"Чушь какая-то..."
Если вы строите конечный автомат – знаете все возможные комбинации параметров на входе и значений на выходе, тогда, казалось бы, куда проще создать карту соответствия.
Однако размер такой карты соответствия, для, казалось бы, простого приложения может и будет занимать непозволительно много места (тривиальный пример – решение шахматной задачи).


Это Вы так думаете, или экспериментально ? Просто у меня уже есть кое-какие экспериментальные данные на графах около 100 000 вызовов функций в приложении. И все выглядит довольно оптимистично. В 30-40% процентов статистических данных функции вызываются повторно с одинаковыми параметрами из-за не идеальности кода. Но это если мыслить в одном измерении, единожды выполненной программы. Но на практике программа запускается многократно, как и сервер выдает одни и теже порции данных, следовательно кеш на уровне многократных запусков программы, броузера, может довести эту цифру до 90% ( пока что я так думаю )

К теме о Шахматах, алгоритм Альфа Бета тем и отличается от Мини Макс что заведомо отсекает ветки с известным результатом. А вот современный комп. не отсекает ... и притармаживает, молотит сто раз одно и тоже.

ALKIR
И, если учесть то, что современный компьютер под управлением современной операционной системы – это не одно приложение, а группа программ, которые "как-то" пытаются сосуществовать и делить ограниченные ресурсы (этого самого компьютера), то задача по определению такой карты соответствия для целого компьютера представляется не разрешимой...


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

ALKIR
Есть еще одно "но", как может показаться начинающему программисту: почему программы выполняют не оптимизированный код. Это происходит потому, что опытные программисты предпочитают использовать код повторно, и пусть этот код написан другими программистами, - главное, что он рабочий.
"Если работает – лучше не трогать..."

В том то и дело, что код повторный. Если бы нельзя было построить древовидный рантайм граф из нескольких тысяч функций, идея была заведомо нереализуема.
...
Рейтинг: 0 / 0
25.11.2009, 13:23:02
    #36330730
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
Хм, как вы собираетесь отлавливать нечто такого типа:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
public Customer CreateCustomer(string name, string surname)
{
       Customer customer=new Customer();
       customer.Name=name;
       customer.Surname=surname;
       customer.RegDate=GetDate();
       return customer;
}
public DateTime GetDate()
{
       return DateTime.Now;
}

Я вижу 2 варианта:
1. Видим что есть нечто непонятное (GetDate()) и отказываемся оптимизировать
2. Видим что есть что-то непонятно(например, вызов другой функции), анализируем ту функцию и проверяем, можем ли запомнить ее. Если можем, то тут тоже можем запомнить. Если же не можем, то обламываемся с мемоизацией всех вызывающих функций, что может привести к довольно печальному результату в виде минимальной эффективности.
3. Ваш вариант?

Кстати, еще вопрос-как собираетесь кешировать вызовы функций к внешним хранилищам (СУБД например). Можно ли запоминать вызов загрузки объекта в случае ORM или нельзя? Или может как-то следить, за тем что объект изменился? Но как тогда вписать все это в единый алгоритм?

Короче, как вы собираетесь мемоизировать функции, которые имеют побочные эффекты и по сути не могут быть просто сведены к функциональному стилю?
...
Рейтинг: 0 / 0
25.11.2009, 13:28:29
    #36330752
zloy den
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
Кстати, императивные программы в большинстве своем вполне (имхо, достаточно реально, если не считать окружающую среду) приводятся к функциональному стилю, думаю можно было бы автоматизировать данный процесс. А еще добавить к полученному функциональному коду профайлер и мемоизировать только те функции, которые действительно в этом нуждаются. А если запихнуть этот код в саму программу, то можно получить автоматически улучшающую свое быстродействие программу (правда остается вопрос-насколько улучшающую?)
...
Рейтинг: 0 / 0
25.11.2009, 13:49:14
    #36330822
sqI
sqI
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
zloy denХм, как вы собираетесь отлавливать нечто такого типа:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
public Customer CreateCustomer(string name, string surname)
{
       Customer customer=new Customer();
       customer.Name=name;
       customer.Surname=surname;
       customer.RegDate=GetDate();
       return customer;
}
public DateTime GetDate()
{
       return DateTime.Now;
}

3. Ваш вариант?



Вот по этому я предлагаю плясать не от структуры ( она обманчива ) а от собственно данных которые проходят через эту структуру. Например если набить статистику по этой функции то выяснится что меняется только один параметр для нее. Но в целом конечно нужно думать.

zloy den
Кстати, еще вопрос-как собираетесь кешировать вызовы функций к внешним хранилищам (СУБД например). Можно ли запоминать вызов загрузки объекта в случае ORM или нельзя? Или может как-то следить, за тем что объект изменился? Но как тогда вписать все это в единый алгоритм?

Короче, как вы собираетесь мемоизировать функции, которые имеют побочные эффекты и по сути не могут быть просто сведены к функциональному стилю?

Или отключить или можно организовать общение с внешними хранилищами подняв снова граф зависимостей или использовав контрольные суммы или последнюю дату с которой данные изменились.
...
Рейтинг: 0 / 0
25.11.2009, 17:29:50
    #36331665
an0nym
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
sqIВот по этому я предлагаю плясать не от структуры ( она обманчива ) а от собственно данных которые проходят через эту структуру. Например если набить статистику по этой функции то выяснится что меняется только один параметр для нее. Но в целом конечно нужно думать.
Или отключить или можно организовать общение с внешними хранилищами подняв снова граф зависимостей или использовав контрольные суммы или последнюю дату с которой данные изменились.
Да не получится. Анализировать только данные на вход и на выход вообще глупость - может функция недетерменированная, но всегда принимает данные и в тех 100 вызовах, которые вы проанализировали, выдавала одинаковые данные, а на 101 выдаст совершенно другие.

Можно или просто - анализировать структуру и иметь эффективность не более 10-20%.
Или сложно - анализировать структуру, данные входные, выходные, анализировать изменение какого параметра как на что влияет - иметь эффективность 90% и или жутко дорогостоящее петабайтное хранилище, куда будут записываться результаты этих анализов и из которого можно быстро получить результаты (скажем 0.00000000000001% данных хранилища) или тратить эти высвобожденные 90% на анализ и через 5 секунд "забывать" результаты этих анализов. Золотую середину уже нашли - она называется многоуровневый кэш процессора + оперативная память.
...
Рейтинг: 0 / 0
25.11.2009, 18:12:07
    #36331826
sqI
sqI
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
an0nym
Да не получится.


Для начала будем говорить о теоретической возможности.

an0nym
Анализировать только данные на вход и на выход вообще глупость - может функция недетерменированная, но всегда принимает данные и в тех 100 вызовах, которые вы проанализировали, выдавала одинаковые данные, а на 101 выдаст совершенно другие.


Функция не черный ящик. У нее есть весьма определенные зависимости от других данных.

an0nym
Можно или просто - анализировать структуру и иметь эффективность не более 10-20%.


При открытии одно и тогоже сайта можно получить эффективность и в 99%. Я могу заверить что граф вызовов функций будет соответстовать на 100%

an0nym
Или сложно - анализировать структуру, данные входные, выходные, анализировать изменение какого параметра как на что влияет - иметь эффективность 90% и или жутко дорогостоящее петабайтное хранилище


Забудьте про петабайты. Их попросту нет.

an0nym
Куда будут записываться результаты этих анализов и из которого можно быстро получить результаты (скажем 0.00000000000001% данных хранилища) или тратить эти высвобожденные 90%
на анализ и через 5 секунд "забывать" результаты этих анализов.


Это говорим о реализации, пока что еще рано.

an0nym
Золотую середину уже нашли - она называется многоуровневый кэш процессора + оперативная память.

Это аппаратное ускорение. Я же предлогаю программное. Разницу наверно обьяснять не нужно в эффективности.
...
Рейтинг: 0 / 0
25.11.2009, 18:43:09
    #36331908
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
Не хотите проанализировать?
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
unsigned int Mand (double initx, double inity, unsigned int iterations) {
    
    double cx,cy,xsq,ysq;
    unsigned int iter;
    
    cx=initx+initx*initx - inity*inity;   
    cy=inity+initx*inity+initx*inity; 
    
    for (iter= 0 ;iter<iterations && (ysq=cy*cy)+(xsq=cx*cx)< 4 ;iter++,cy=inity+cx*cy+cx*cy,cx=initx-ysq+xsq) ;
    return (iter);
}
...
Рейтинг: 0 / 0
25.11.2009, 19:26:28
    #36331982
sqI
sqI
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
DocAlНе хотите проанализировать?
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
unsigned int Mand (double initx, double inity, unsigned int iterations) {
    
    double cx,cy,xsq,ysq;
    unsigned int iter;
    
    cx=initx+initx*initx - inity*inity;   
    cy=inity+initx*inity+initx*inity; 
    
    for (iter= 0 ;iter<iterations && (ysq=cy*cy)+(xsq=cx*cx)< 4 ;iter++,cy=inity+cx*cy+cx*cy,cx=initx-ysq+xsq) ;
    return (iter);
}


А что тут сложного. Строишь таблицу зависимостей.
Код: plaintext
double initx, double inity, unsigned int iterations, Result

У тебя тут нет глобальных переменных.
...
Рейтинг: 0 / 0
25.11.2009, 19:33:59
    #36331996
DocAl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Почему компьютер выполняет 90% лишней работы ?
Угу, закэшируйте, пожалуйста, множество Мандельброта...
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Почему компьютер выполняет 90% лишней работы ? / 25 сообщений из 55, страница 1 из 3
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]