- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
// =================================================================================================
//
// Starling Framework
// Copyright 2011 Gamua OG. All Rights Reserved.
//
// This program is free software. You can redistribute and/or modify it
// in accordance with the terms of the accompanying license agreement.
//
// =================================================================================================
package starling.utils
{
/** Returns the next power of two that is equal to or bigger than the specified number. */
public function getNextPowerOfTwo(number:int):int
{
if (number > 0 && (number & (number - 1)) == 0) // see: http://goo.gl/D9kPj
return number;
else
{
var result:int = 1;
while (result < number) result <<= 1;
return result;
}
}
}
Для кого-то и логарифм - высшая математика... :(
Follow us!
ширина / высота - целые числа. :)
Он бы сдвиг сделал. Инфа 100%.
Кстати, зря в языках нету bsr
Тем более, функция используется в атласе текстур, где все измерения целочисленные и неотрицательные.
Если для этого логарифм не использовать, то для чего же тогда? Тут прямо и само название говорит об этом.
Код автора - лучше. Сдвиговая арифметика.
А дорогое деление и логарифм, а также перессылка в st0 и обратно съедят скорость.
Есть более быстрые способы, но они юзают битовую магию и неочевидны для читателей.
>где все измерения целочисленные и неотрицательные.
Тем более.
Минус.
Вроде как нет, хотя и близко. Ну и пришлось немного подправить исходный вариант, т.как не работал.
Да и вообще в этом месте скорость была вообще не принципиальна. Атлас текстур собирается и разбирается не так часто, ну и вычислить именно это значение в контексте сборки атласа - вообще ни на что не повлияет по сравнению со временем нужным на то, чтобы скопировать текстуру в нужное место и загрузить атлас в память.
Ну и чем тогда железобетонный и наглядный код со сдвигами хуже логарифма?
P.S. Вот всяко на нормальном компилируемом языке он еще и быстрее.
Кстати, если уж речь о байтолюбстве, то есть еще такие варианты:
Как оказалось, бинарный поиск - в пролете, а обычный if-else всех победил.
Да, получится чуть быстрее.
Но, тут еще такой момент: самый первый тест я сделал в более старой версии плеера, где логарифм вообще выигал, а в более новой - он безнадежно проигрывает. Т.е. видимо где-то в JIT компиляции научились лучше понимать байткод.
Кроме того, бинарный поиск можно оптимизировать, но для этого нужно будет переписать это на HaXe, или использовать какой-нибудь "оптимизатор", который бы переделал чтение / запись из флешевого вектора в обычный Си-шный массив. Скорее всего время тратится именно там в бинарном поиске.
Есть одна асмокоманда. Но она не поддерживается ни в одном известном мне ЯВУ.
http://ideone.com/vODZhq
На соответствующих процах компилится именно в bsr. На тех где нету - видимо в цикл.
Ещё байтоёбский вопрос: запилят ли в стандарт mul_int_int_to_double_int и div_double_int_on_int?
> запилят ли в стандарт
146%, что нет.
> А в LLVM запилят?
__builtin_ia32_bsrdi. Х.з. если честно как с ним не на интелях.
> mul_int_int_to_double_int и div_double_int_on_int
Если я правильно понял, что double int это тупо два инта - то тут gcc и так отлично справляется. Где-то я уже кидал пример который превращается в одинокий imul.
Чудеса конечно. Но asmовставка очевидней будет.
int __builtin_popcount (unsigned int x)
Ну то давно известно. На многие случаи жизни, особенно когда дело касается работы с битами есть "одна асмокомманда".
Например еще есть popcnt и lzcnt. Последняя суть аналог bsr, но вроде побыстрее.
Я же о реализации без них.
Вот реально жаль что в языках нету команды которая делит число и одновременно находит его остаток. Всё какие-то проценты сраные.
Кстати мне раньше нравилась старая winApi функция mulDiv, которую дельфятники даже в язык встроили. Но это немного не то.
А они всякое не особо нужное говно добавляют.
Умножение по модулю? Ну да, для той же криптографии полезно.
div когда делит, то результат деления в eax, а остаток в edx.
Обожаю эту фичу.
Потому что обычно когда делишь, то нужен и остаток. А везде надо 2 деления делать. Это говно.
>Умножение по модулю?
Это mulDiv. Или не то выделил когда цитировал?
Делает список из 2-х значений?
Где первый элемент - частное, а второе остаток?
Это моя очепятка :)
>чуда-макрос
чудо-макрос
А то как я только не пробовал
(format t "a: ~d, b: ~d~&" (a, b) ))
(format t "a: ~d, b: ~d~&" a, b ))
А там оказывается хуйня с делением.
P.S. За название multiple-value-bind мне хочется взять-и-уебать того кто ее так назвал. Довольно удобная и полезная фича, которую тем не менее противно юзать из-за длинного имени.
fixed :)
> Это mulDiv. Или не то выделил когда цитировал?
Да, на mulDiv отвечал.
Но, блядь, почему в лоу-левельной сишке и прочих языках такого нет?
Ладно - они не могут в кортежи, списки и возвращать несколько значений.
Но ведь есть же передача по ссылке.
ну а ссылок в сишке нет, указатели только
Да. Асм безусловно рулит в таких вопросах. Быстро и красиво.
Кстати тут очень давно это обсуждали.
"суть наверное в том чел написал одну годную оптимизацию
> (number & (number - 1))
Но не написал другую
Но когда я дошел до Math.floor(Math.log(x) / Math.log(2)) понял что код абсолютно адекватен.
Вот буквально только что смотрел. Из сырцов жабы (довольно свежих):
ConcurrentHashMap.class - очень годная, скоростная мапа, если что.
За что эта константа отвечает?
а вот жабу не знаешь, раз ответить не смог
- Неа.
- Нет? А на си-решетке сидел?
- Нет.
- Че, крестоблядь что-ли?
Одно дело знать жабу, другое знать все кишки реализации ее хешмапов.
Битовая магия, не?
Можно номер строки в которой она находится?
Дело в том что нам надо "округлять вверх" до ближайшего сдвига. То есть задача следующая
min(x,y where y=2^n and y>x)
Работа кода вполне соответствует комменту:
/** Returns the next power of two that is equal to or bigger than the specified number. */
P.S. Ну правда next можно было и убрать.
Да, согласен.
Заодно отвечая гумну. Чтобы мапа хорошо асспараллелилась, то её бьют на сегменты, на каждый сегмент своя лочка.
От хеша отрезают часть адреса и отводят на сегмент, остальное на адрес внутри - классика.
Так вот нам надо найти минимальную степень двойки, которая покроет нужный concurrencyLevel
Потому берем либо точно, либо немного с избытком. BUT NOT ANYMORE BABY!!!
Это ж должно быть очевидно - почему так.
Edit. Вон и bormand чуть выше толкует об том же.
Блять. И вот после они говорят, что в кресты добавили поддержку многопоточности в новом стандарте С++11. Даже в бородавках жабы есть потокобезопасные контейнеры
Другое дело быстрый, потокобезопастный контейнер, который умеет раssпаралеливаться - то есть можно одновременно добавлять значения, с другого треда читать, а с третьего удалять. Разработка такой штуки - дело непростое.
Потому кстати это одно из немногих мест где шарп отстал от жабы - в до-диезе только с 4-ой версии добавили ConcurrentDictionary. А до этого у них был только тормозной Hashtable.Synchronised, который работал в однопоточном режиме. Нахуй так жить?
а парни из интела даже пропозицию делали в стандарт по поводу concurrent_* контейнеров
proposal?
Концепты
«Концепты» (concepts) – это механизм, описывающий требования для типов, комбинаций типов или комбинаций типов и целых чисел. Эта возможность особенно полезна для ранней проверки использования шаблонов. И наоборот, она также помогает находить ошибки в теле шаблона на ранней стадии. Давайте рассмотрим алгоритм fill из стандартной библиотеки:
// типы типов
template<ForwardIterator Iter, class V>
// взаимоотношения между аргументами типов
requires Assignable<Iter::value_type,V>
// лишь объявление, а не определение
void fill(Iter first, Iter last, const V& v);
// Iter имеет тип int; ошибка: int не является ForwardIterator-ом
// int не содержит *
fill(0, 9, 9.9);
// Iter имеет тип int; ok: int* является ForwardIterator-ом
fill(&v[0], &v[9], 9.9);
· Аргументы first и last должны быть типом ForwardIterator (и они должны быть одного типа).
· Третий аргумент v должен быть типом, который можно присвоить типу value_type типа ForwardIterator.
Конечно, мы все это знаем, ведь мы читали стандарт. Однако, компиляторы не умеют читать документы с требованиями, поэтому мы должны сказать ему в коде, в виде концептов ForwardIterator и Assignable. В результате ошибки использования метода fill() могут быть пойманы в месте использования, и текст ошибок может быть значительно яснее. Теперь у компилятора есть информация о намерениях программиста, что позволяет обеспечить хороший уровень проверок и диагностических сообщений.
Эта ошибка будет отловлена сразу же, устраняя необходимость трудоемкого тестирования (хотя и не избавляет от тестирования полностью).
С возможностью классифицировать и различать разные типы типов, мы можем перегружать методы, основываясь на виде передаваемых типов. Например:
Вы можете определить свои собственные концепты, но для начала, в стандартной библиотеке определен большой набор полезных концептов, таких как ForwardIterator, Collable, LessThanComparable и Regular.
Обратите внимание, стандартные библиотеки С++11 предусматривают использование концептов.
См. также:
the C++ draft 14.10 Concepts
[N2617=08-0127] Douglas Gregor, Bjarne Stroustrup, James Widman, and Jeremy Siek: Proposed Wording for Concepts (Revision 5) (Final proposal).
Douglas Gregor, Jaakko Jarvi, Jeremy Siek, Bjarne Stroustrup, Gabriel Dos Reis, and Andrew Lumsdaine: Concepts: Linguistic Support for Generic Programming in C++. OOPSLA'06, October 2006.
int* является ForwardIterator; мы сказали об этом при обсуждении концептов, и в стандартной библиотеке это всегда было именно так; даже в первой версии STL указатели использовались в качестве итераторов. Однако, мы также говорили о члене value_type типа ForwardIterator. Но int* не содержит члена с именем value_type; на самом деле, он вообще не содержит никаких членов. Так как int* может быть ForwardIterator? Поскольку мы сами это указали. С помощью concept_map мы можем сказать, что при использовании T*, где требуется ForwardIterator, мы будем рассматривать T в качестве value_type:
concept_map позволяет указать способ представления нашего типа, предотвращая от модификации существующий тип или от создания нового типа в качестве обертки. «Отображения концептов» (concept maps) являются гибким и обобщенным механизмом для адаптации независимо разработанных программ для совместного использования.
the C++ draft 14.10.2 Concept maps
[N2617=08-0127] Douglas Gregor, Bjarne Stroustrup, James Widman, and Jeremy Siek: Proposed Wording for Concepts (Revision 5) (Final proposal).
Douglas Gregor, Jaakko Jarvi, Jeremy Siek, Bjarne Stroustrup, Gabriel Dos Reis, Andrew Lumsdaine: Concepts: Linguistic Support for Generic Programming in C++. OOPSLA'06, October 2006.
Аксиома (axiom) – это набор предикатов, определяющих семантику концепта. Главным сценарием использование аксиом являются внешние инструменты (например, действия, нетипичные для компилятора), такие как, инструменты для предметно-ориентированных оптимизаций (domain-specific optimizations) (языки для описания программных изменений стали важным поводом появления аксиом). Аксиомы также могут быть полезны для некоторых оптимизаций (выполняемых компилятором и обычными оптимизаторами), но компиляторы не должны обращать внимания на пользовательские аксиомы; их работа основана на семантиках, определенных в стандарте.
Аксиомы перечисляют пару вычислений, которые могут трактоваться как эквивалентные. Например:
concept
<=> - это оператор эквивалентности, используемый только в аксиомах. Обратите внимание, что вы не можете (в общем случае) доказать аксиому; мы используем аксиомы для указания того, что мы не можем доказать, но что программист может назвать приемлемым допущением. Обратите внимание, что обе стороны оператора эквивалентности могут быть некорректными для некоторых значений, например использование NaN (not a number) для типов с плавающей запятой: если обе стороны эквивалентности используют NaN, то обе стороны (явно) некорректны и эквивалентны (независимо от того, что говорится в аксиоме), но если NaN используется только с одной стороны, то существует возможность получить выгоды от использования аксиомы.
// в концепте TotalOrder:
axiom Transitivity(Op op, T x, T y, T z)
{
// условная эквивалентность
if (op(x, y) && op(y, z)) op(x, z) <=> true;
}
См. также:
the C++ draft 14.9.1.4 Axioms
???.
Зато они приняли std::atomic, который в нормальных локфри алгоритмах и не поиспользуешь нормально.
в частности, последние proposalы по интересующей тебя теме датируются сентябрем 2012 (кстати, в авторах числится А. Малахов - может поэтому не принимают?) http://bit.ly/SgjoTp
а вообще в целом интересная страничка:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/
А не AssParallel() #pragma omp parallel for для быдла которое возомнило что может в многопоточность.
Я серъезно.
Ладно. Я сегодня добрый.
Примерно такая же как между мутабельной ссылкой на массив констант, и константым массивом мутабельных переменных.
http://stackoverflow.com/questions/692677/atomicintegerarray-vs-atomicinteger
AtomicInteger[] is an array of thread safe integers.
AtomicIntegerArray is a thread-safe array of integers.
AtomicIntegerArray is a thread-safe array of integers.
Похоже на записки из бортового журнала капитана-очевидность.
Yes.
Поэтому AtomicIntegerArray быстрее, жрет меньше памяти, и его проще инициализировать.
У эрланга, правда, есть большое преимущество: посколько процессы не шарят память, можно осуществлять сборку мусора в софт-реалтайм режиме: собирать мусор в тех процессах, которые в данный момент не выполняются, позволяя активным процессам продолжать работу.
Можно все делать в одном модуле, в одном потоке, чтобы никуда ничего не передавать :) но это как-бы делает потоки и все что с ними связано бесполезным.
И это приводит к неимоверно кривым решениям:
- запись в файл и передача имени файла (так и то быстрее получается).
- запись в базу данных, и передавать доступ к соединению с базой в разные потоки (ппц глючно).
- держать открытый сокет с самопальным сервером, предназначенным для хранения информации (типа Memcached, например). Тоже решение так себе, т.как обычно уже лучше написать и обработку там же заодно.
Есть другой, меньший недостаток. Все объекты представлены, как в жабоскрипте: список, а внутри еще список, а внутри еще список... и т.д. Когда объекты простенькие - все замечательно, а когда начинаются усложнения - records превращаются в страницы текста до боли похожие одна на другую. И тут паттерн-матчинг начинает работать против нас, т.как случайно ненужные объекты попадают не в те функции. Решение - люди начинают изобретать свои системы типизации, которые, как правило сводятся к тому, что первым елементом в списке идет какой-нибудь символ, по которому дальше уже выбирается, что нужно. Естесственно, проблемы с уникальностью таких символов, ну и куча бойлерплейта, который никак не скрыть.
Зачем передавать измененный список полностью, если можно передать комманду на изменение копии списка, находящегося в чужом экторе?
Эм. А рекордов там нет?
Просто храни список экторов (они у нас будут заменять рекорды) и через сообщения выпытывай у них значения тех или иных полей.
Конечно, если программировать на эрланге, как на стандартных парадигмах - оно не будет работать.
Можно конечно не посылать им весь спискок, а послать "что поменялось", и пусть сами разбираются как обновить список. Таким образом экономим память, но тратим время на то, что каждая функция выполнит ту же процедуру по изменению списка.
Т.е. получается, что проигрываем либо по памяти, либо по скорости.
> Стандартных парадигмах
Каких стандартов? :)
Работать, как уже было заявлено, будет в песочнице, по-настоящему - не будет.
> Рекорды
Ну вот они аналогичны жабоскриптовскому Object, в рантайме они неотличимы один от другого. Т.е. чтобы понять, что перед нами объект какого-то определенного типа нам нужно проверить, что все требования к типу соблюдены, при чем сделать это вручную. Т.е. если это пользователь чата, то нужно проверить, что у него есть имя, возраст, адресс и т.д. Даже всякие самодельные, не встроенные в язык системы типа той же eieio берут на себя этот тяжкий труд и предоставляют красивый способ решить эту проблему. В Эрланге, это все нужно делать самому, но в виду вышеописаных обстоятельств делать и не хочется особо, т.как никакой выгоды в перспективе не намечается.
Заводим процесс на каждого клиента, процесс на каждый диалог (который привязан к процессам клиентов). При смене состояния клиента (поменялся статус/отвалился) процесс диалога получает оповещение, и рассылает всем остальным участникам диалога соответствующее сообщение.
Если нужно делать постоянные вычисления и выборки по условиям, можно не мучиться с ручным удалением из списков и хранить данные в in-memory таблицах mnesia.
Проектировать распределённые системы сложно: нужно тщательно продумывать, кто за что отвечает и какие сообщения кому посылает, но в этом есть особенный кайф.
От разделяемого состояния на самом деле профита немного. При любом раскладе всем клиентам (ICQ-клиентам, comet-страничкам, etc.) нужно рассылать нотификации об изменении статусов, и наличие глобального состояния на сервере тут ничем не поможет. Оно также помешает распределению сервера по нескольким машинам.
Вывод: картинку нужно хранить где-то отдельно, и каким-то образом косвенно разрешать другим функциям с ней работать, так чтобы они эту картинку никогда по-настоящему не получали. Эта стратегия так быстро перерастает в неимоверное мозгоебство, с которым ну так не хочется бороться, особенно, когда рядом лежит нормальный инструмент, которы может это сделать вообще без затрачивания каких-либо усилий.
Возможно, если очень упорно стараться сделать то же самое на Эрланге, можно каким-то образом построить систему, которая не будет передавать ресурсы, а только записывать в них чего-то. Но зачем? Нет ничего, что бы Эрланг делал лучше чем аналоги. Издеваться над собой ради чего?
Сопоставление с образцом? Так оно и не нужно в 90% случаев, и еще в 9% случаев работает не так, как нужно.
Ключевые слова для создания процессов + ппц неудобная конструкция их обработки? - Офигенный бонус. Я прям зальюсь слезами и все брошу когда вместо receive мне нужно будет написать reactor.callLater(...)
>Erlang
No way.
Стандартная стратегия при работе с эктерами. Чего плохого то? Какие проблемы вызывает? Я бы так и на другом языке делал. Просто с этим эктером обменивался сообщениями.
Или, просто, напишите фильтр "размывка", который усредняет значения цвета в пикселах без чтения из картинки.
А вот та идея, что обсуждается ниже (хранение кучи копий рисунков) - вообще не работоспособна. Это вместо единой работы, мы загружаем процессор кучой копий работы. А ведь это не единственная проблема. Результат некоторых алгоритмов рисования зависит от порядка рисования элементов. То есть если один человек закончил контур, а второй заливал этот контур (могло быть наоборот и команды пришли в обратном порядке), то залилось лишнее или один рисовал линию, а второй размытие (опять же в зависимости от порядка прихода команд), то линия получится размытой или нет. Порядок прихода сообщений в эрланге одному эктору от разных экторов не определен. Это значит что в каждой копии окажется свой рисунок, отличаюийся от других рисунков, если тебе не повезло. Делать так, чтобы один видел одно, а другой другое - глупо. Один говорит - ты все правильно сделал, а другой чатится с криками - ты упорот штоле? Лучше пусть они имеют единое мнение о упоротости или кутости параллельно рисующих. И отменят неудавшиеся операции.
Первый этап делаем по технологии map-reduce, а второй на основе перового уже как финальная обработка. Конечно этапов можно завести и больше, если нужно.
Сервер, разумеется, ничего отрисовывать не должен, лишь заниматься маршрутизацией команд. Аналогично решается зача коллективного редактирования текста: между клиенскими машинами и сервером должны бегать только небольшие (но частые) патчи.
chatroulette.com
В сервере написаном на Эрланге юзабилити будет не просто убогий, он вообще работать не будет :) даже проверять бессмысленно.
пф, что это
Это совсем другая задача - не коллективное редактирование документов, а передача потока, и этим занимаются высокооптимизированные медиа-сервера, написанные на плюсах или на том же эрланге (http://erlyvideo.org/). Предварительной обработки там не требуется: получил поток, направь его в нужную соску. Сервер там ничего не рендерит, и никаких фильтров не применяет.
И тут на клиенте как раз стоит жирный Flash Player.
Вот именно потому, что не применяет никаких фильтров, да и вообще ничего толком с видео сделать не может - и не нужен он по большому счету. Я же почему чатрултеку вспомнил. Там очень даже нужно с видео что-то делать.
Например, там даже есть ИИ который пытается (но не очень успешно ;) угадать показывает ли абонент свои гениталии в камеру или это у него лицо такое. Но там еще много чего в том же духе.
А вот это интересно. Можно поподробнее?
Если рендерить всё на сервере, передавать изображения между разными процессами тоже практически не нужно.
На каждого клиента будет процесс, который принимает от него команды на редактирование; на каждое "коллективное" изображение будет процесс, который отвечает за последовательное применение команд, и практически не делит ни с кем изображение, разве что с процессом, отправляющим изображение обратно пользователям.
Кстати, бинарные данные в сообщениях не копируются в рамках одного нода: можно спокойно передавать блоб с изображением от процесса к процессу, копироваться будет только кортеж, в который завернули бинарник.
А проблема всплывает в обработке изображения на erlang: для каждой команды нужно будет порождать новую копию изображения, что не эффективно для большого числа мелких команд, да и эрланг слишком тормозной для обработки изображений. Кстати, эрланговцы сами честно не советуют применять его для этого:
The most common class of 'less suitable' problems is characterised by performance being a prime requirement and constant-factors having a large effect on performance. Typical examples are image processing, signal processing, sorting large volumes of data and low-level protocol termination.
http://www.erlang.org/faq/introduction.html
Когда сопоставление с образцом вредно:
- у нас есть кортеж, который представляет пользователя, мы написали функции которые на нем сепциализируется узнавая первый элемент коретжа как символ 'user'. Приложение монетизируют следующим образом: пользователи с "премиум" возможностями могут совершать какие-то операции, другие пользователи не могут (за эти возможности они чего-то заплатили).
Проблема: кортежи, которые представляют платных пользователей нужно как-то отличать от обычных пользователей.
Если мы переименуем первый тег в 'premium_user' - все функции, которые раньше специализировались на 'user' нужно либо переписать, либо они не будут рабоать. Иногда нам нужно / не важно будут ли они работать с новым типом пользователей, а может быть и важно. Другой вариант, оставляем и тех и других с тегом 'user' и добавляем еще один элемент в кортеж, в котором указываем тип пользователя - но проблему это не решает, т.как переписывать все равно нужно много. Можно еще использовать эрланговское наследование, при условии, что все функции работающие с пользователями были в одном модуле (а как же...) это будет немного лучше.
Вобщем, работа с похожими, но не одинаковыми объектами становится головной болью номер один, и выглядит как либо огромное количество if-ов, а учитывая не-ленивые if-ы, это цирк тот еще... Или в кучу служебных функций, которые пытаются как-то отфильтровать нужные типы объектов, или сигнатуры функций начинают выглядеть как доказательство последней теоремы Ферма.
Я бы в таком случае, наверное, попытался применить список привилегий пользователя.