Бэкдор для Skype похищает данные

Исследователи Palo Alto Networks обнаружили бэкдор, способный похищать из Skype видео, аудио, сообщения и скриншоты.
По данным экспертов, зловред T9000, прилагает большие усилия, чтобы оставаться незамеченным. Он относится к семейству Plat1 и применяется в фишинговых атаках против ряда американских организаций.

Для запуска процедуры установки T9000 пользователю нужно открыть вредоносный файл .rtf, полученный в фишинговом сообщении. Многоступенчатый процесс инсталляции позволяет зловреду избежать детектирования.
Сначала T9000 тщательно выявляет, установлена ли в системе одна из 24 программ обеспечения безопасности (Sophos, INCAInternet, DoctorWeb, Baidu, Comodo, TrustPortAntivirus, GData, AVG, BitDefender, VirusChaser, McAfee, Panda, Trend Micro, Kingsoft, Norton, Micropoint, Filseclab, AhnLab, JiangMin, Tencent, Avira, Kaspersky, Rising и 360), и уже после адаптирует процесс загрузки таким образом, чтобы обойти защиту.
На второй стадии загружается вредоносная DLL-библиотека, при этом бэкдор снова проверяет, какой из антивирусов может представлять для него угрозу. В зависимости от результатов проверки зловред применяет один из трех возможных сценариев для начала третьей фазы. Сам вредоносный компонент загружается не раньше четвертой фазы, но даже тогда T9000 способен незаметно исчезнуть, не оставляя следов, если выявит в системе запущенные процессы антивирусных программ. Если же установка увенчалась успехом, имя пользователя и версия ОС отправляются на удаленный сервер, с которого, в свою очередь, загружаются модули, позволяющие злоумышленникам похищать данные.

Первый из них делает скриншоты экрана каждые 20 секунд и собирает информацию из Skype. Если Skype запущен, злоумышленник обманом заставляет жертву предоставить разрешение на доступ к Skype исполняемому файлу explorer.exe, иначе атака не сработает. В случае успеха атакующий получает возможность записи аудио- и видеозвонков и сбора текстовых сообщений.
Но этим T9000 не ограничивается: он крадет документы формата .doc, .ppt, .xls, .docx, .pptx, .xlsx, в том числе со съемных дисков. За это отвечает другой плагин — FlaskDiskThief.
Третий плагин нужен для ведения журнала изменений файлов: вредоносный компонент отслеживает, когда файл был создан, копирован, перемещен или удален.

По мнению исследователей, атакующим нужны эти данные, чтобы изучить поведение жертвы, что в конечном итоге может дать им полезные сведения для «углубления» атаки. В Palo Alto уже опубликовали список индикаторов атаки и надеются, что в ближайшее время появится способ противостоять зловреду, а пока советуют пользователям быть особо внимательными, так как ключевым элементом атаки является согласие пользователя дать соответствующие разрешения вредоносному приложению.

Больше информации:

http://ift.tt/1QmD0T1
http://ift.tt/211lB9J

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Работа с данными: Новая наука

Объемы научных данных увеличиваются с поразительной скоростью, потому появляется необходимость в новых математических методах и методах анализа. Наборы данных становятся все больше и сложнее во многих дисциплинах, связанных, например, с нейронными сетями, астрофизикой или медициной.

Физик из Северо-Восточного университета (США) Алессандро Веспиньяни (Alessandro Vespignani) занимается моделированием поведения фондового рынка, предсказанием результатов выборов и другими статистическими задачами. В его распоряжении находятся несколько терабайт данных, полученных из социальных сетей, и почти все они [данные] неструктурированные.

Для обработки собранных данных Веспиньяни использует широкий набор математических инструментов и методов. Он сортирует миллионы твитов и проводит поиск по ключевым словам. Веспиньяни эффективно используют поэтапный подход к анализу больших данных. Однако математик Йельского университета Рональд Койфман (Ronald Coifman) утверждает, что недостаточно просто собирать и хранить громадные объемы информации, их нужно грамотно организовывать, а для этого нужна специальная структура.

Вершины и ребра

Возникший в XIII веке город Кёнигсберг (ныне Калининград) состоял из трёх формально независимых городских поселений, которые были расположены на островах и берегах реки Преголи, делящей город на четыре главные части. Эти четыре участка земли соединялись между собой семью мостами. В XVIII веке математик Леонард Эйлер ломал голову над популярной в то время загадкой: как пройти по всем семи мостам Кёнигсберга и вернуться в начальную точку, не ступая по каждому из мостов дважды?

Чтобы ее решить, Эйлер построил модель из точек и линий и обнаружил, что задача имеет решение только в том случае, если к каждому «островку земли» будет вести четное количество мостов. Так как в Кёнигсберге было нечетное количество мостов, это путешествие оказалось невозможным.

Взяв за основу идею Эйлера, математик Стэндфордского университета Гуннар Карлссон (Gunnar Carlsson) начал строить карты данных, представляя громоздкие наборы данных как сеть из вершин и ребер. Подход называется топологическим анализом данных (TDA – Topological Data Analysis), и, по словам Гуннара, «позволяет структурировать неструктурированные данные, чтобы в последствии проанализировать их методами машинного обучения». На видео Карлссон объясняет, как топологический анализ помогает исследователям интерпретировать большие наборы данных.

Как и в случае с задачкой про мосты, здесь все «связано» со связями, простите за каламбур. Социальные сети – это карта взаимоотношений между людьми, где вершинами являются имена, а ребрами – связи. Карлссон считает, что этот подход можно использовать в других сферах, например, для работы с геномными последовательностями. «Можно сравнить последовательности и выявить количество различий. Полученное число можно представить как функцию расстояния, которая будет показывать, насколько сильно они отличаются», – объясняет Карлссон.

Проект Карлссона Ayasdi создан именно для этого: он позволяет упрощать представление данных высокой размерности. Если ваш многоразмерный набор данных имеет 155 переменных, то как будет выглядеть запрос, учитывающий их все и разом? Карлссон сравнивает эту задачу с поиском молотка в темном гараже. Если у вас есть фонарик, то вы будете последовательно просматривать содержимое гаража, пока не наткнетесь на нужный вам инструмент – этот процесс достаточно долгий и может вывести вас из себя. Гораздо эффективнее включить свет – вы сразу найдете и молоток, и коробку гвоздей, хоть вы и не подозревали, что они вам понадобятся. Технология Ayasdi как раз зажигает лампочку.

Применяя топологические методы, мы словно проецируем сложный объект на плоскость. Опасность заключается в том, что некоторые закономерности — словно иллюзии в театре теней, и на самом деле не существуют. Более того, ряд учёных полагает, что к некоторым наборам данных топологические методы вообще неприменимы. Если ваш набор данных искажен или неполон, то они могут дать совершенно некорректные результаты.

Бритва Оккама

В феврале 2004 года математик Стэндфордского университета Эммануэль Кандес (Emmanuel Candes) пытался найти способ улучшить размытое изображение. Кандес применил один из разработанных алгоритмов и ожидал увидеть незначительные улучшения, однако перед ним предстала четкая картинка. По словам Кандеса, вероятность этого равнялась вероятности угадать десять цифр номера банковской карты, зная первые три. Но то была не случайность. Метод сработал и с другими изображениями.

Ключом к успеху стала, так сказать, математическая версия бритвы Оккама: из миллионов возможных вариантов реконструкции конкретного нечеткого изображения лучше всего подойдет самая простая версия. Это открытие породило метод Compressed sensing.

Сегодня он применяется в видеотрансляциях по сети. Количество данных при передаче видео так огромно, что приходится их сжимать. Обычно для того, чтобы сжать данные, необходимо сначала получить все биты, а затем отбросить незначимые. Метод Compressed sensing позволяет определить значимые биты, не требуя предварительного их сохранения.

«Если я провожу скрининг населения на наличие редкого заболевания, нужны ли мне анализы крови всех людей? Ответ – нет. Достаточно провести лишь несколько испытаний, поскольку искомый «фактор» встречается очень редко, то есть является разреженным», – отметил Кандес. Предположим, что у нас есть один зараженный в группе из 32 человек. У каждого из них мы взяли кровь на анализ. Если тест отрицательный, то инфицированных нет. Но если результат положительный, то как найти зараженного?

Кандес считает, что можно взять половину образцов (16) и провести повторный анализ. Если результат положительный, то инфицированный находится в этой группе, если нет, то в другой. Далее группа снова делится пополам, и тестирование повторяется. Таким образом, вы получите ответ за 5 тестов, вместо 32, если проверять каждого по отдельности. В этом суть метода Compressed sensing.

Метод Compressed sensing может помочь в работе с большими наборами данных, часть которых была утеряна или повреждена. Хорошим примером будет обработка медицинских записей, в части которых имеют опечатки, допущенные персоналом поликлиники. Еще один пример – система распознавания лиц: если человек наденет очки, его все равно можно будет узнать.

Пока Кандес превозносит методику Compressed sensing, Карлссон придерживается топологического подхода. Однако эти два метода лишь дополняют друг друга, но никак не конкурируют. «В конце концов, наука о данных – это нечто большее, чем просто сумма методологий, – настаивает Веспиньяни. – Объединив несколько методов, мы сможем создать что-то совершенно новое».

P.S. Совсем недавно мы публиковали подборку источников по машинному обучению для начинающих и рассказывали про глубокое обучение. Конечно, мы делимся и собственным опытом: немного о разработке системы квантовой связи и о том, как из простых студентов готовят продвинутых программистов.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Вложенные привязки в WPF

В WPF существует три вида привязок: Binding, PriorityBinding и MultiBinding. Все три привязки наследуются от одного базового класса BindingBase. PriorityBinding и MultiBinding позволяют к одному свойству привязать несколько других привязок, например:

<MultiBinding Converter="{StaticResource JoinStringConverter}" ConverterParameter=" ">
    <Binding Path="FirstName" />
    <Binding Path="MiddleName" />
    <Binding Path="LastName" />
</MultiBinding>

Исходный код класса JoinStringConverter

public class JoinStringConverter : IMultiValueConverter
{
    public object Convert(object[] values, Type targetType, object parameter, CultureInfo culture)
    {
        var separator = parameter as string ?? " ";
        return string.Join(separator, values);
    }

    public object[] ConvertBack(object value, Type[] targetTypes, object parameter, CultureInfo culture)
    {
        var separator = parameter as string ?? " ";
        return (value as string)?.Split(new[] { separator }, StringSplitOptions.None).Cast<object>().ToArray();
    }
}

Список привязок MultiBinding-а — это коллекция типа Collection<BindingBase>. Логично было бы предположить, что внутри MultiBinding-а можно использовать еще один MultiBinding.

<MultiBinding Converter="{StaticResource JoinStringConverter}" ConverterParameter=" ">
    <Binding Path="MyProperty1" />
    <MultiBinding Converter="{StaticResource JoinStringConverter}" ConverterParameter=", ">
        <Binding Path="MyProperty2" />
        <Binding Path="MyProperty3" />
        <Binding Path="MyProperty4" />
    </MultiBinding>
</MultiBinding>

Но при выполнении такого кода ловим исключение "BindingCollection не поддерживает элементы типа MultiBinding. Допускается только тип Binding.". Зачем же было тогда использовать Collection<BindingBase>, а не Collection<Binding>? А потому, что если использовать Collection<Binding>, мы бы поймали другое исключение "Binding нельзя использовать в коллекции «Collection<Binding>». «Binding» можно задать только в параметре DependencyProperty объекта DependencyObject.".

Для решения проблемы вложенных привязок был написан класс NestedBinding, который позволяет использовать внутри себя другие привязки Binding и NestedBinding.

Исходный код класса NestedBinding

[ContentProperty(nameof(Bindings))]
public class NestedBinding : MarkupExtension
{
    public NestedBinding()
    {
        Bindings = new Collection<BindingBase>();
    }

    public Collection<BindingBase> Bindings { get; }

    public IMultiValueConverter Converter { get; set; }

    public object ConverterParameter { get; set; }

    public CultureInfo ConverterCulture { get; set; }

    public override object ProvideValue(IServiceProvider serviceProvider)
    {
        if (!Bindings.Any())
            throw new ArgumentNullException(nameof(Bindings));
        if (Converter == null)
            throw new ArgumentNullException(nameof(Converter));

        var target = (IProvideValueTarget)serviceProvider.GetService(typeof(IProvideValueTarget));
        if (target.TargetObject is Collection<BindingBase>)
        {
            var binding = new Binding
            {
                Source = this
            };
            return binding;
        }

        var multiBinding = new MultiBinding
        {
            Mode = BindingMode.OneWay
        };
        var tree = GetNestedBindingsTree(this, multiBinding);
        var converter = new NestedBindingConverter(tree);
        multiBinding.Converter = converter;

        return multiBinding.ProvideValue(serviceProvider);
    }

    private static NestedBindingsTree GetNestedBindingsTree(NestedBinding nestedBinding, MultiBinding multiBinding)
    {
        var tree = new NestedBindingsTree
        {
            Converter = nestedBinding.Converter,
            ConverterParameter = nestedBinding.ConverterParameter,
            ConverterCulture = nestedBinding.ConverterCulture
        };
        foreach (var bindingBase in nestedBinding.Bindings)
        {
            var binding = bindingBase as Binding;
            var childNestedBinding = binding?.Source as NestedBinding;
            if (childNestedBinding != null && binding.Converter == null)
            {
                tree.Nodes.Add(GetNestedBindingsTree(childNestedBinding, multiBinding));
                continue;
            }

            tree.Nodes.Add(new NestedBindingNode(multiBinding.Bindings.Count));
            multiBinding.Bindings.Add(bindingBase);
        }

        return tree;
    }
}

Исходный код классов NestedBindingNode и NestedBindingsTree

public class NestedBindingNode
{
    public NestedBindingNode(int index)
    {
        Index = index;
    }

    public int Index { get; }

    public override string ToString()
    {
        return Index.ToString();
    }
}

public class NestedBindingsTree : NestedBindingNode
{
    public NestedBindingsTree() : base(-1)
    {
        Nodes = new List<NestedBindingNode>();
    }

    public IMultiValueConverter Converter { get; set; }

    public object ConverterParameter { get; set; }

    public CultureInfo ConverterCulture { get; set; }

    public List<NestedBindingNode> Nodes { get; private set; }
}

Исходный код класса NestedBindingConverter

public class NestedBindingConverter : IMultiValueConverter
{
    public NestedBindingConverter(NestedBindingsTree tree)
    {
        Tree = tree;
    }

    private NestedBindingsTree Tree { get; }

    public object Convert(object[] values, Type targetType, object parameter, CultureInfo culture)
    {
        var value = GetTreeValue(Tree, values, targetType, culture);
        return value;
    }

    private object GetTreeValue(NestedBindingsTree tree, object[] values, Type targetType, CultureInfo culture)
    {
        var objects = tree.Nodes.Select(x => x is NestedBindingsTree ? GetTreeValue((NestedBindingsTree)x, values, targetType, culture) : values[x.Index]).ToArray();
        var value = tree.Converter.Convert(objects, targetType, tree.ConverterParameter, tree.ConverterCulture ?? culture);
        return value;
    }

    public object[] ConvertBack(object value, Type[] targetTypes, object parameter, CultureInfo culture)
    {
        throw new NotImplementedException();
    }
}

Реализован NestedBinding через обычный MultiBinding. Но т.к. MultiBinding не может принимать другой MultiBinding, то дерево разворачивается в список Binding-ов. Позиция этих Binding-ов и их конвертеры сохраняются для дальнейшей генерации исходного дерева в конвертере NestedBindingConverter.

Конвертер получает список значений всех привязок Binding и структуру исходного дерева. Далее рекурсией производится обход дерева, и вычисляются значения конвертеров.

Пример использования NestedBinding:

<TextBlock>
    <TextBlock.Text>
        <n:NestedBinding Converter="{StaticResource JoinStringConverter}" ConverterParameter=", ">
            <Binding Path="A" />

            <n:NestedBinding Converter="{StaticResource JoinStringConverter}" ConverterParameter=" ">
                <Binding Path="B" />
                <Binding Path="C" />

                <n:NestedBinding Converter="{StaticResource JoinStringConverter}" ConverterParameter="">
                    <Binding Source="(" />
                    <Binding Path="D" />
                    <Binding Path="E" />
                    <Binding Source=")" />
                </n:NestedBinding>
            </n:NestedBinding>

            <Binding Path="F" UpdateSourceTrigger="PropertyChanged" />
        </n:NestedBinding>
    </TextBlock.Text>
</TextBlock>

На выходе получаем строку «A, B C (DE), F».

Исходники выложены в репозитории GitHub.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Обстоятельно о подсчёте единичных битов

Я хотел бы подарить сообществу Хабра статью, в которой стараюсь дать достаточно полное описание подходов к алгоритмам подсчёта единичных битов в переменных размером от 8 до 64 битов. Эти алгоритмы относятся к разделу так называемой «битовой магии» или «битовой алхимии», которая завораживает своей красотой и неочевидностью многих программистов. Я хочу показать, что в основах этой алхимии нет ничего сложного, и вы даже сможете разработать собственные методы подсчёта единичных битов, познакомившись с фундаментальными приёмами, составляющими подобные алгоритмы.

Прежде чем мы начнём, я сразу хочу предупредить, что это статья не для новичков в программировании. Мне необходимо, чтобы читатель в общих чертах представлял себе простейшие битовые операции (побитовое «и», «или», сдвиг), хорошо владел шестнадцатеричной системой счисления и достаточно уверенно пользовался воображением, представляя в нём не всегда короткие битовые последовательности. По возможности, всё будет сопровождаться картинками, но сами понимаете, они лишь упрощают, но не заменяют полное представление.

Все описанные приёмы были реализованы на языке Си и протестированы в двух режимах: 32 и 64 бита. Таким образом, для более полного понимания статьи будет лучше, чтобы вы хотя бы приблизительно понимали язык Си. Тестирование проходило на процессоре Core 2 Duo E8400 @3GHz на 64-х битовой Windows 7. Измерение чистого времени работы программ проводилось с помощью утилиты runexe. Все исходные коды описываемых алгоритмов доступны в архиве на Яндекс диске, их компиляция проверена для компиляторов Visual C++, Intel C++, GCC и CLang, так что в принципе, проблем у вас быть не должно, если кто-то захочет перепроверить результаты у себя. Пользователи Linux, думаю, лучше меня знают, как им тестировать время работы программы у себя в системе, поэтому им советов не даю.

Среди читателей, возможно, будут такие, кому проще посмотреть всё то же самое на видео. Я записал такое видео (58 минут), в котором в формате презентации изложено в точности всё то же самое, что будет ниже по тексту, но может немного в другом стиле, более сухо и строго, тогда как текст я попытался немного оживить. Поэтому изучайте материал так, как кому удобнее.

Смотреть видео

Сейчас будут последовательно описаны алгоритмы, порождаемые тем или иным набором алхимических приёмов, в каждом разделе будет таблица сравнения времени работы для переменных разного размера, а в конце будет сводная таблица по всем алгоритмам. Во всех алгоритмах используются псевдонимы для чисел без знака от 8 до 64 бит.

typedef unsigned char      u8;
typedef unsigned short int u16;
typedef unsigned int       u32;
typedef unsigned long long u64;

Наивный подход

Очевидно, что битовая алхимия применяется вовсе не для того, чтобы блистать на собеседовании, а с целью существенного ускорения программ. Ускорения по отношению к чему? По отношению к тривиальным приёмам, которые могут прийти в голову, когда нет времени более детально вникнуть в задачу. Таковым приёмом и является наивный подход к подсчёту битов: мы просто «откусываем» от числа один бит за другим и суммируем их, повторяя процедуру до тех пор, пока число не станет равным нулю.

u8 CountOnes0 (u8 n) {
  u8 res = 0;
  while (n) {
    res += n&1;
    n >>= 1;
  }
  return res;
}

Я не вижу смысла что-либо комментировать в этом тривиальном цикле. Невооружённым взглядом ясно, что если старший бит числа n равен 1, то цикл вынужден будет пройтись по всем битам числа, прежде чем доберётся до старшего.

Меняя тип входного параметра u8 на u16, u32 и u64 мы получим 4 различные функции. Давайте протестируем каждую из них на потоке из 2³² чисел, подаваемых в хаотичном порядке. Понятно, что для u8 у нас 256 различных входных данных, но для единообразия мы всё равно прогоняем 2³² случайных чисел для всех этих и всех последующих функций, причём всегда в одном и том же порядке (за подробностями можно обратиться к коду учебной программы из архива).

Время в таблице ниже указано в секундах. Для тестирования программа запускалась трижды и выбиралось среднее время. Погрешность едва ли превышает 0,1 секунды. Первый столбец отражает режим компилятора (32-х битовый исходный код или 64-х битовый), далее 4 столбца отвечают за 4 варианта входных данных.

Режим	u8	u16	u32	u64
x86	38,18	72,00	130,49	384,76
x64	37,72	71,51	131,47	227,46

Как мы видим, скорость работы вполне закономерно возрастает с ростом размера входного параметра. Немного выбивается из общей закономерности вариант, когда числа имеют размер 64 бита, а подсчёт идёт режиме x86. Ясное дело, что процессор вынужден делать четырёхкратную работу при удвоении входного параметра и даже хорошо, что он справляется всего лишь втрое медленнее.

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

Трюк с «откусыванием» младших единичных битов

Этот алхимический приём основан на идее обнуления младшего единичного бита. Имея число n, мы можем произнести заклинание n=n&(n-1), забирая у числа n его младшую единичку. Картинка ниже для n=232 прояснит ситуацию для людей, впервые узнавших об этом трюке.

Код программы не сильно изменился.

u8 CountOnes1 (u8 n) {
  u8 res = 0;
  while (n) {
    res ++;
    n &= n-1;  // Забираем младшую единичку.
  }
  return res;
}

Теперь цикл выполнится ровно столько раз, сколько единиц в числе n. Это не избавляет от худшего случая, когда все биты в числе единичные, но значительно сокращает среднее число итераций. Сильно ли данный подход облегчит страдания процессора? На самом деле не очень, а для 8 бит будет даже хуже. Напомню, что сводная таблица результатов будет в конце, а здесь в каждом разделе будет своя таблица.

Режим	u8	u16	u32	u64
x86	44,73	55,88	72,02	300,78
x64	40,96	69,16	79,13	126,72

Предподсчёт

Не будем торопиться переходить к «жёстким» заклинаниям, рассмотрим последний простой приём, который может спасти даже самого неопытного мага. Данный вариант решения задачи не относится напрямую к битовой алхимии, однако для полноты картины должен быть рассмотрен в обязательном порядке. Заведём две таблицы на 256 и 65536 значений, в которых заранее посчитаны ответы для всех возможных 1-байтовых и 2-байтовых величин соответственно.

  u8 BitsSetTableFF[256];     // Здесь все ответы для одного байта
  u8 BitsSetTableFFFF[65536]; // Здесь все ответы для двух байт

Теперь программа для 1 байта будет выглядеть так

  u8 CountOnes2_FF (u8 n) {
    return BitsSetTableFF[n];
  }

Чтобы рассчитать число бит в более крупных по размеру числах, их нужно разбить на байты. Например, для u32 может быть вот такой код:

  u8 CountOnes2_FF (u32 n) {
    u8 *p = (u8*)&n;
    n = BitsSetTableFF[p[0]]
      + BitsSetTableFF[p[1]]
      + BitsSetTableFF[p[2]]
      + BitsSetTableFF[p[3]];
    return n;
  }

Или такой, если мы применяем таблицу предподсчёта для 2-х байт:

  u8 CountOnes2_FFFF (u32 n) {
    u16 *p = (u16*)&n;
    n = BitsSetTableFFFF[p[0]]
      + BitsSetTableFFFF[p[1]];
    return n;
  }

Ну а дальше вы догадались, для каждого варианта размера входного параметра n (кроме 8 бит) может существовать два варианта предподсчёта, в зависимости от того, которую из двух таблиц мы применяем. Думаю, читателю понятно, почему мы не можем просто так взять и завести таблицу BitsSetTableFFFFFFFF, однако вполне могут существовать задачи, где и это будет оправданным.

Быстро ли работает предподсчёт? Всё сильно зависит от размера, смотрите таблицы ниже. Первая для однобайтового предподсчёта, а вторая для двухбайтового.

Режим	u8	u16	u32	u64
x86	0,01	1,83	21,07	36,25
x64	0,01	1,44	24,79	26,84

Интересный момент: для режима x64 предподсчёт для u64 работает заметно быстрее, возможно, это особенности оптимизации, хотя подобное не проявляется во втором случае.

Режим	u8	u16	u32	u64
x86	---	0,05	7,95	13,01
x64	---	0,07	8,49	13,01

Важное замечание: данный алгоритм с использованием предподсчёта оказывается выгодным только лишь при соблюдении следующих двух условий: (1) у вас есть лишняя память, (2) вам требуется выполнять расчёт числа единичных битов намного больше раз, чем размер самой таблицы, то есть имеется возможность «отыграть» время, потраченное на предварительное заполнение таблицы каким-то из нехитрых алгоритмов. Пожалуй, можно также иметь в виду экзотическое условие, которое на практике всегда выполнено. Вы должны гарантировать, что обращение к памяти само по себе быстрое и не замедляет работу других функций системы. Дело в том, что обращение к таблице может выбросить из кэша то, что там было изначально и замедлить таким образом какой-то другой участок кода. Косяк это вы вряд ли найдёте быстро, однако подобные чудовищные оптимизации едва ли кому-то понадобятся на практике при реализации обычных программ.

Умножение и остаток от деления

Возьмем же наконец более сильные зелья с нашей алхимической полки. С помощью умножения и остатка от деления на степень двойки без единицы можно делать довольно интересные вещи. Начнём творить заклинание с одного байта. Для удобства обозначим все биты одного байта латинскими буквами от «a» до «h». Наше число n примет вид:

Умножение n' = n⋅0x010101 (так, через префикс «0x», я обозначаю шестнадцатеричные числа) делает ни что иное как «тиражирование» одного байта в трёх экземплярах:

Теперь разобьём мысленно наши 24 бита на 8 блоков по 3 бита в каждом (см. нижеследующую картинку, первую строку таблички). Затем с помощью побитового «и» с маской 0x249249 (вторая строка таблички) обнулим в каждом блоке два старших бита.

Третья строка таблицы поясняет шестнадцатеричную запись маски. В последней строке показан результат, которого мы добивались: все биты исходного байта содержаться каждый в своём трёхбитовом блоке, но в ином порядке (порядок нам и не важен).

Теперь внимание: мы должны сложить эти 8 блоков – и получим сумму наших бит!

Оказывается, что остаток от деления некоторого числа A на 2^k-1 как раз даёт сумму k-битовых блоков числа A, тоже взятую по модулю 2^k-1.

Пруф

Разобьём число A (в двоичной записи) на блоки по k бит в каждом (при необходимости можно дополнить самый последний, старший, блок нулями). Обозначим через A_i i-й блок. Теперь запишем значение числа A через сумму этих блоков, помноженных на соответствующую степень двойки:
A= A₀⋅2^0⋅k+ A₁⋅2^1⋅k+…+ A_N-1⋅2^(N-1)⋅k,
где N – число блоков.
Теперь рассчитаем A mod (2^k-1).
A mod (2^k-1)= (A₀⋅2^0⋅k+ A₁⋅2^1⋅k+…+ A_N-1⋅2^(N-1)⋅k) mod (2^k-1) = (A₀+ A₁+…+ A_N-1) mod (2^k-1).
Всё благодаря тому, что 2^i⋅k = 1 (mod (2^k-1)) для любого целого неотрицательного i. (Здесь, правда, важно, что трюк имеет смысл, когда k>1, иначе не совсем понятно как нам интерпретировать модуль 1). Вот мы и получили сумму блоков по модулю 2^k-1.

То есть от полученного нами числа нужно взять остаток от деления на 2³-1 (семь) — и мы получаем сумму наших 8-и блоков по модулю 7. Беда в том, что сумма бит может быть равна 7 или 8, в таком случае алгоритм выдаст 0 и 1 соответственно. Но давайте посмотрим: в каком случае мы можем получить ответ 8? Только когда n=255. А в каком случае можем получить 0? Только когда n=0. Поэтому если алгоритм после взятия остатка на 7 даст 0, то либо мы на входе получили n=0, либо в числе ровно 7 единичных бит. Суммируя эту рассуждение, получаем следующий код:

u8 CountOnes3 (u8 n) {  
  if (n == 0)  return 0;  // Единственный случай, когда ответ 0.
  if (n == 0xFF)  return 8;  // Единственный случай, когда ответ 8.
  n = (0x010101*n & 0x249249) % 7;  // Считаем число бит по модулю 7.
  if (n == 0)  return 7;  // Гарантированно имеем 7 единичных битов.
  return n;  // Случай, когда в числе от 1 до 6 единичных битов.
}  

В случае когда n имеет размер 16 бит можно разбить его на две части по 8 бит. Например, так:

u8 CountOnes3 (u16 n) {  
  return CountOnes3 (u8(n&0xFF)) + CountOnes3 (u8(n>>8));

Для случая 32-х и 64-х бит подобное разбиение не имеет смысла уже даже в теории, умножение и остаток от деления с тремя ветвлениями будут слишком дорого стоить, если выполнять их 4 или 8 раз подряд. Но я оставил для вас пустые места в нижеследующей таблице, поэтому если вы мне не верите – заполните их, пожалуйста, сами. Там скорее всего будут результаты, сравнимые с процедурой CountBits1, если у вас похожий процессор (я не говорю о том, что здесь возможны оптимизации с помощью SSE, это уже будет другой разговор).

Режим	u8	u16	u32	u64
x86	12,42	30,57	---	---
x64	13,88	33,88	---	---

Данный трюк, конечно, можно сделать и без ветвлений, но тогда нам нужно, чтобы при разбиении числа на блоки в блок вместились все числа от 0 до 8, а этого можно добиться лишь в случае 4-битовых блоков (и больше). Чтобы выполнить суммирование 4-битовых блоков, нужно подобрать множитель, который позволит правильно «растиражировать» число и взять остаток от деления на 2⁴-1=15, чтобы сложить получившиеся блоки. Опытный алхимик (который знает математику) легко подберёт такой множитель: 0x08040201. Почему он выбран таким?

Дело в том, что нам необходимо, чтобы все биты исходного числа заняли правильные позиции в своих 4-битовых блоках (картинка выше), а коль скоро 8 и 4 не являются взаимно простыми числами, обычное копирование 8 битов 4 раза не даст правильного расположения нужных битов. Нам придётся добавить на нашему байту один нолик, то есть тиражировать 9 битов, так как 9 взаимно просто с 4. Так мы получим число, имеющее размер 36 бит, но в котором все биты исходного байта стоят на младших позициях 4-битовых блоков. Осталось только взять побитовое «и» с числом 0x111111111 (вторая строка на картинке выше), чтобы обнулить по три старших бита в каждом блоке. Затем блоки нужно сложить.

При таком подходе программа подсчёта единичных битов в байте будет предельно простой:

u8 CountOnes3_x64 (u8 n) {
  return ((u64)0x08040201*n & 0x111111111) % 15;
}

Недостаток программы очевиден: требуется выход в 64-битовую арифметику со всеми вытекающими отсюда последствиями. Можно заметить, что в действительности данная программа задействует только 33 бита из 64-х (старшие 3 бита обнуляются), и в принципе можно сообразить, как перенести данные вычисления в 32-х битовую арифметику, но рассказы о подобных оптимизациях не входят в тему этого руководства. Давайте пока просто изучать приёмы, а оптимизировать их вам придётся самим уже под конкретную задачу.

Ответим на вопрос о том, какого размера может быть переменная n, чтобы данный трюк правильно работал для неё. Коль скоро мы берём остаток от деления на 15, такая переменная не может иметь размер больше 14 бит, в противном случае придётся применить ветвление, как мы делали это раньше. Но для 14 бит приём работает, если добавить к 14-ти битам один нолик, чтобы все биты встали на свои позиции. Теперь я буду считать, что вы в целом усвоили суть приёма и сможете сами без труда подобрать множитель для тиражирования и маску для обнуления ненужных битов. Покажу сразу готовый результат.

u8 CountOnes3_x64 (u14 n) { // Это не опечатка (и не должно работать)!
  return (n*0x200040008001llu & 0x111111111111111llu) % 15;
}

Эта программа выше показывает, как мог бы выглядеть код, будь у вас переменная размером 14 бит без знака. Этот же код будет работать с переменной в 15 бит, но при условии, что максимум лишь 14 из них равные единице, либо если случай, когда n=0x7FFF мы разберём отдельно. Это всё нужно понимать для того, чтобы написать правильный код для переменной типа u16. Идея в том, чтобы сначала «откусить» младший бит, посчитать биты в оставшемся 15-ти битовом числе, а затем обратно прибавить «откушенный» бит.

static u8 CountOnes3_x64 (u16 n) {  
  u8 leastBit = n&1;  // Берём младший бит.
  n >>= 1;  // Оставляем только 15 бит исходного числа.
  if (n == 0)  return leastBit; // Если получился 0, значит ответом будет младший бит.
  if (n == 0x7FFF)  return leastBit + 15; // Единственный случай, когда ответ 15+младший бит.
  return leastBit + (n*0x200040008001llu & 0x111111111111111llu) % 15;  // Ответ (максимум 14+младший бит).
}

Для n размером 32 бита приходится колдовать уже с более серьёзным лицом… Во-первых, ответ влезает только в 6 бит, но можно рассмотреть отдельный случай, когда n=2³²-1 и спокойно делать расчёты в полях размером 5 бит. Это экономит место и разрешает нам разбить 32-битовое поле числа n на 3 части по 12 бит в каждой (да, последнее поле будет не полным). Поскольку 12⋅5=60, мы можем тиражировать одно 12-битовое поле 5 раз, подобрав множитель, а затем сложить 5-битовые блоки, взяв остаток от деления на 31. Сделать это нужно 3 раза для каждого поля. Суммируя итог, получаем такой код:

static u8 CountOnes3_x64 ( u32 n ) {    
  if (n == 0)  return 0;
  if (n + 1 == 0)  return 32;
  u64 res = (n&0xFFF)*0x1001001001001llu & 0x84210842108421llu;
  res += ((n&0xFFF000)>>12)*0x1001001001001llu & 0x84210842108421llu;
  res += (n>>24)*0x1001001001001llu & 0x84210842108421llu;
  res %= 0x1F;
  if (res == 0)  return 31;
  return res;
}

Здесь точно также можно было вместо трех ветвлений взять 3 остатка от деления, но я выбрал ветвистый вариант, на моём процессоре он будет работать лучше.

Для n размером 64 бита мне не удалось придумать подходящего заклинания, в котором было бы не так много умножений и сложений. Получалось либо 6, либо 7, а это слишком много для такой задачи. Другой вариант — выход в 128-битовую арифметику, а это уже не пойми каким «откатом» для нас обернётся, неподготовленного мага может и к стенке отшвырнуть :)

Давайте лучше посмотрим на время работы.

Режим	u8	u16	u32	u64
x86	39,78	60,48	146,78	---
x64	6,78	12,28	31,12	---

Очевидным выводом из этой таблицы будет то, что 64-х битовая арифметика плохо воспринимается в 32-х битовом режиме исполнения, хотя в целом-то алгоритм неплох. Если вспомнить скорость алгоритма предподсчёта в режиме x64 для однобайтовой таблицы для случая u32 (24,79 с), то получим, что данный алгоритм отстаёт всего лишь на 25%, а это повод к соревнованию, воплощённому в следующем разделе.

Замена взятия остатка на умножение и сдвиг

Недостаток операции взятия остатка всем очевиден. Это деление, а деление – это долго. Разумеется, современные компиляторы знают алхимию и умеют заменять деление на умножение со сдвигом, а чтобы получить остаток, нужно вычесть из делимого частное, умноженное на делитель. Тем не менее, это всё равно долго! Оказывается, что в древних свитках заклинателей кода сохранился один интересный способ оптимизации предыдущего алгоритма. Мы можем суммировать k-битовые блоки не взятием остатка от деления, а ещё одним умножением на маску, с помощью которой обнуляли лишние биты в блоках. Вот как это выглядит для n размером в 1 байт.

Для начала снова тиражируем байт трижды и удаляем по два старших бита у каждого 3-битового блока с помощью уже пройденной выше формулы 0x010101⋅n & 0x249249.

Каждый трёхбитовый блок я для удобства обозначил заглавной латинской буквой. Теперь умножаем полученный результат на ту же самую маску 0x249249. Маска содержит единичный бит в каждой 3-й позиции, поэтому такое умножение эквивалентно сложению числа самого с собой 8 раз, каждый раз со сдвигом на 3 бита:

Что мы видим? Биты с 21 по 23 и дают нам нужную сумму! При этом переполнения в каком-либо из блоков справа невозможно, так как там ни в одном блоке не будет числа, большего 7. Проблема лишь в том, что если наша сумма равна 8, мы получим 0, но это не страшно, ведь этот единственный случай можно рассмотреть отдельно.

u8 CountOnes3_x64_m (u8 n) {  
  if (n == 0xFF)  return 8;
  return ((u64(0x010101*n & 0x249249) * 0x249249) >> 21) & 0x7;
}

По сути, мы взяли код из предыдущего раздела и заменили в нём взятие остатка от деления на 7 на умножение, сдвиг и побитовое «И» в конце. При этом вместо 3-х ветвлений осталось лишь одно.

Чтобы составить аналогичную программу для 16 бит, нам нужно взять код из предыдущего раздела, в котором показано как это делается с помощью взятия остатка от деления на 15 и заменить данную процедуру умножением. При этом нетрудно заметить то, какие условия можно убрать из кода.

u8 CountOnes3_x64_m (u16 n) {    
  u8 leastBit = n&1; // Берём младший бит
  n >>= 1; // Оставляем только 15 бит.
  return leastBit
  + (( (n*0x200040008001llu & 0x111111111111111llu)*0x111111111111111llu 
       >> 56) & 0xF); // Ответ (максимум 15 + младший бит).
}

Для 32-х бит мы делаем то же самое: берём код из предыдущего раздела и, порисовав немного на бумаге, соображаем, каким будет сдвиг, если заменить остаток на умножение.

u8 CountOnes3_x64_m ( u32 n ) {    
  if (n+1 == 0)  return 32;
  u64 res = (n&0xFFF)*0x1001001001001llu & 0x84210842108421llu;
  res += ((n&0xFFF000)>>12)*0x1001001001001llu & 0x84210842108421llu;
  res += (n>>24)*0x1001001001001llu & 0x84210842108421llu;
  return (res*0x84210842108421llu >> 55) & 0x1F;
}

Для 64-х бит я тоже не смог придумать чего-то такого, чтобы не заставляло бы мой процессор выполнять роль печки.

Режим	u8	u16	u32	u64
x86	12,66	42,37	99,90	---
x64	3,54	4,51	18,35	---

Приятно удивили результаты для режима x64. Как и ожидалось, мы обогнали предподсчёт с однобайтовой таблицей для случая u32. Можно ли вообще обогнать предподсчёт? Хороший вопрос :)

Параллельное суммирование

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

Начнём с 1 байта. Байт состоит из 4-х полей по 2 бита, сначала просуммируем биты в этих полях, произнеся что-то вроде:

n = (n>>1)&0x55 + (n&0x55);

Вот пояснительная картинка к данной операции (по-прежнему, обозначаем биты одного байта первыми латинскими буквами):

Одно из побитовых «И» оставляет только младшие биты каждого двухбитового блока, второе оставляет старшие биты, но сдвигает их на позиции, соответствующие младшим битам. В результате суммирования получаем сумму смежных битов в каждом двухбитовом блоке (последняя строка на картинке выше).

Теперь сложим парами числа, находящиеся в двухбитовых полях, помещая результат в 2 четырёхбитовых поля:

n = (n>>2)&0x33 + (n&0x33);

Нижеследующая картинка поясняет результат. Привожу её теперь без лишних слов:

Наконец, сложим два числа в четырёхбитовых полях:

n = (n>>4)&0x0F + (n&0x0F);

Действуя по аналогии, можно распространить приём на любое число бит, равное степени двойки. Число строк заклинания равно двоичному логарифму от числа бит. Уловив идею, взгляните вскользь на 4 функции, записанных ниже, чтобы убедиться в правильности своего понимания.

u8 CountOnes4 (u8 n) {
  n = ((n>>1) & 0x55) + (n & 0x55);
  n = ((n>>2) & 0x33) + (n & 0x33);
  n = ((n>>4) & 0x0F) + (n & 0x0F);
  return n;
}

u8 CountOnes4 (u16 n) {
  n = ((n>>1) & 0x5555) + (n & 0x5555);
  n = ((n>>2) & 0x3333) + (n & 0x3333);
  n = ((n>>4) & 0x0F0F) + (n & 0x0F0F);
  n = ((n>>8) & 0x00FF) + (n & 0x00FF);
  return n;
}

u8 CountOnes4 (u32 n) {
  n = ((n>>1) & 0x55555555) + (n & 0x55555555);
  n = ((n>>2) & 0x33333333) + (n & 0x33333333);
  n = ((n>>4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F);
  n = ((n>>8) & 0x00FF00FF) + (n & 0x00FF00FF);
  n = ((n>>16) & 0x0000FFFF) + (n & 0x0000FFFF);
  return n;
}

u8 CountOnes4 (u64 n) {
  n = ((n>>1) & 0x5555555555555555llu) + (n & 0x5555555555555555llu);
  n = ((n>>2) & 0x3333333333333333llu) + (n & 0x3333333333333333llu);
  n = ((n>>4) & 0x0F0F0F0F0F0F0F0Fllu) + (n & 0x0F0F0F0F0F0F0F0Fllu);
  n = ((n>>8) & 0x00FF00FF00FF00FFllu) + (n & 0x00FF00FF00FF00FFllu);
  n = ((n>>16) & 0x0000FFFF0000FFFFllu) + (n & 0x0000FFFF0000FFFFllu);
  n = ((n>>32) & 0x00000000FFFFFFFFllu) + (n & 0x00000000FFFFFFFFllu);
  return n;
}

На этом параллельное суммирование не заканчивается. Развить идею позволяет то наблюдение, что в каждой строчке дважды используется одна и та же битовая маска, что как будто наводит на мысль «а нельзя ли как-нибудь только один раз выполнить побитовое «И»?». Можно, но не сразу. Вот что можно сделать, если взять в качестве примера код для u32 (смотрите комментарии).

u8 CountOnes4 (u32 n) {
  n = ((n>>1) & 0x55555555) + (n & 0x55555555);  // Можно заменить на разность
  n = ((n>>2) & 0x33333333) + (n & 0x33333333); // Нельзя исправить
  n = ((n>>4) & 0x0F0F0F0F) + (n & 0x0F0F0F0F); // Можно вынести & за скобку
  n = ((n>>8) & 0x00FF00FF) + (n & 0x00FF00FF); // Можно вынести & за скобку
  n = ((n>>16) & 0x0000FFFF) + (n & 0x0000FFFF); // Можно вообще убрать &
  return n; // Неявное обрезание по 8-и младшим битам.
}

В качестве упражнения я бы хотел предложить доказать самостоятельно то, почему нижеследующий код будет точным отображением предыдущего. Для первой строки я даю подсказку, но не смотрите в неё сразу:

Подсказка

Двухбитовый блок ab имеет точное значение 2a+b, значит вычитание сделает его равным…?

u8 CountOnes4_opt (u32 n) {
  n -= (n>>1) & 0x55555555;
  n = ((n>>2) & 0x33333333 ) + (n & 0x33333333);
  n = ((n>>4) + n) & 0x0F0F0F0F;
  n = ((n>>8) + n) & 0x00FF00FF;
  n = ((n>>16) + n);
  return n;
}

Аналогичные варианты оптимизации возможны и для остальных типов данных.

Ниже приводятся две таблицы: одна для обычного параллельного суммирования, а вторая для оптимизированного.

Режим	u8	u16	u32	u64
x86	7,52	14,10	21,12	62,70
x64	8,06	11,89	21,30	22,59

Режим	u8	u16	u32	u64
x86	7,18	11,89	18,86	65,00
x64	8,09	10,27	19,20	19,20

В целом мы видим, что оптимизированный алгоритм работает хорошо, но проигрывает обычному в режиме x86 для u64.

Комбинированный метод

Мы видим, что наилучшие варианты подсчёта единичных битов – это параллельный метод (с оптимизацией) и метод тиражирования с умножением для подсчёта суммы блоков. Мы можем объединить оба метода, получая комбинированный алгоритм.

Первое, что нужно сделать — выполнить первые три строки параллельного алгоритма. Это даст нам точную сумму битов в каждом байте числа. Например, для u32 выполним следующее:

  n -= (n>>1) & 0x55555555;
  n = ((n>>2) & 0x33333333) + (n & 0x33333333);
  n = (((n>>4) + n) & 0x0F0F0F0F );

Теперь наше число n состоит из 4 байт, которые следует рассматривать как 4 числа, сумму которых мы ищем:

Мы можем найти сумму этих 4-х байт, если умножим число n на 0x01010101. Вы теперь хорошо понимаете, что означает такое умножение, для удобства определения позиции, в которой будет находиться ответ, привожу картинку:

Ответ находится в 3-байте (если считать их от 0). Таким образом, комбинированный приём для u32 будет выглядеть так:

u8 CountOnes5 ( u32 n ) {
  n -= (n>>1) & 0x55555555;
  n = ((n>>2) & 0x33333333 ) + (n & 0x33333333);
  n = ((((n>>4) + n) & 0x0F0F0F0F) * 0x01010101) >> 24;
  return n; // Здесь происходит неявное обрезание по 8 младшим битам.
}

Он же для u16:

static u8 CountOnes5 (u16 n) {
  n -= (n>>1) & 0x5555;
  n = ((n>>2) & 0x3333) + (n & 0x3333);
  n = ((((n>>4) + n) & 0x0F0F) * 0x0101) >> 8;
  return n; // Здесь происходит неявное обрезание по 8 младшим битам.
}

Он же для u64:

u8 CountOnes5 ( u64 n ) {
  n -= (n>>1) & 0x5555555555555555llu;
  n = ((n>>2) & 0x3333333333333333llu ) + (n & 0x3333333333333333llu);
  n = ((((n>>4) + n) & 0x0F0F0F0F0F0F0F0Fllu)
       * 0x0101010101010101) >> 56;
  return n; // Здесь происходит неявное обрезание по 8 младшим битам.
}

Скорость работы этого метода вы можете посмотреть сразу в итоговой таблице.

Итоговое сравнение

Я предлагаю читателю самостоятельно сделать интересующие его выводы, изучив две нижеследующие таблицы. В них я обозначил название методов, программы к которым мы реализовали, а также пометил прямоугольной рамкой те подходы, которые я считаю наилучшими в каждом конкретном случае. Тех, кто думал, что предподсчёт всегда выигрывает, ожидает небольшой сюрприз для режима x64.

Итоговое сравнения для режима компиляции x86.

Итоговое сравнения для режима компиляции x64.

Замечание

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

Я изложил те идеи, о которых знаю сам, но это лишь идеи, конкретные реализации которых в разных комбинациях могут быть очень разными. Объединяя эти идеи разными способами, вы можете получать огромное количество разных алгоритмов подсчёта единичных битов, каждый из которых вполне может оказаться хорошим в каком-то своём случае.

Спасибо за внимание. До новых встреч!

UPD: Инструкция POPCNT из SSE4.2 не включена в список тестирования, потому что у меня нет процессора, который поддерживает SSE4.2.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Go sync.Pool

Вольный пересказ документации к sync.Pool
Сборщик мусора (далее GC) не постоянно собирает мусор, а через определённые промежутки времени. В случае если ваш код выделяет память под некоторые структуры данных, а потом освобождает их — и так по кругу — это вызывает определённое давление на GC, в том числе заставляет runtime обратиться к ОС для выделения новой памяти. Представьте: выделяем кусок (например []byte), работаем с ним, освобождаем. Пройдёт определённое время, прежде GC "очнётся ото сна" и соберёт этот кусок. Если в это время мы выделим ещё один такой же кусок и уже выделенной у ОС памяти на это не хватит, то приложение будет вынуждено запросить у ОС ещё памяти. По времени приложения запрос памяти у ОС длится вечность. А в это самое время где-то пылится, ждёт своего часа тот прежний "отработанный" кусок.
Что же делать?

• создать пул
• сбрасывать состояние куска
• складывать в пул отработанные куски
• брать новые куски из пула

Создать пул

import(
    "sync"
)

var bytesPool = sync.Pool{
    New: func() interface{} { return []byte{} },
}

/*
В данном примере функция `New` не нужна. Если пул пуст,
и `New` не `nil` - то она будет использована для создания нового
объекта. Его нужно будет преобразовать из `interace{}` - привести
к нужному типу. Смотри ниже - про это есть децл.
*/

Сбросить состояние

// пусть ary у нас []byte определённой длины и ёмкости
ary = ary[:0]
// усекаем len, сохраняем cap

Положить в пул

/*
так или иначе у нас могут оказаться слишком большие куски,
которые в принципе нам не понадобятся (во всяком случае
не часто) - выбросим их; иначе: кусок размером 2048 байт
будет использоваться там где нужно всего 500-800 байт,
при большом количестве это негативно отразится на памяти
- а ведь мы с этим и боремся
*/
const maxCap = 1024

if cap(ary) <= maxCap {
    // кладём в пул куски ограниченного размера
    bytesPool.Put(ary)
}

Взять из пула

nextAry := bytesPool.Get().([]byte)

Пояснение про New

Функция New создаёт пустой []byte{}, да ещё и эти преобразования в interface{} и обратно. В случае с []byte мы скорее всего будем наращивать его с помощью append, что в принципе делает такой подход не выгодным:

• создание []byte нулевой ёмкости
• двойное преобразование в interface{} и обратно
• append всё равно создаст новый кусок
• append можно скормить nil, только типа []byte (а не interface{})

Гораздо удобней сделать две функции, которые бы занимались всей вознёй с пулом

// получить
func getBytes() (b []byte) {
    ifc := bytesPool.Get()
    if ifc != nil {
        b = ifc.([]byte)
    }
    return
}
// положить
func putBytes(b []byte) {
    if cap(b) <= maxCap {
        b = b[:0] // сброс
        bytesPool.Put(b)
    }
}

Помните

• sync.Pool не панацея
• пул горутино-безопасен
• пул не обязательно освободит данные при первом пробуждении GC, но он может освободить их в любой момент
• нет возможности определить и установить размер пула
• нет необходимости заботится о переполнении пула
• вовсе незачем городить пул везде где ни попади, он создавался как амортизатор при множественном совместном использовании некоторых общих объектов, даже не просто внутри пакета, а даже больше — другими пакетами
• вероятно у Вас есть или будут ситуации, когда необходимость/возможность помочь GC будет очевидной
• пул ограниченного размера делается с помощью канала с буфером

Хороший пример использования пула: пакет fmt. Со 109-ой по 150-ую строку.

---

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

[Перевод] Почему я больше не использую MVC-фреймворки

Опубликовано с большого одобрения автора и согласия портала infoq.com. Надеюсь, мои языковые навыки оправдают оказанное автором доверие.

Худшее в моей работе на сегодняшний день, это проектирование API для front-end разработчиков. Диалог с ними неизбежно разворачивается следующим образом:

Dev — итак, на этом экране нужны данные x, y и z. Не мог бы ты сделать API, которое вернет данные в формате {x:, y:, z: }

Я — ok

Я больше даже не спорю с ними. Проекты заканчивается ворохом различных API, привязанных к экранам, которые меняются очень часто, что “by design” требует изменений в API. Вы и глазом моргнуть не успеваете, а у вас уже куча API и для каждого необходимо поддерживать множество форматов и платформ. Сэм Ньюман даже начал формализовывать этот подход как BFF Pattern, предполагающий, что это нормально — разрабатывать отдельное API для каждого типа устройства, платформы и, естественно, каждой версии вашего приложения. Дэниэл Якобсон рассказывал, что Netflix был вынужден начать использовать новую характеристику для своего “Experience API”: эфемерность. Ох…

Пару месяцев назад я начал свой путь в поисках ответа на вопрос, почему все так сложилось и что с этим делать. Этот путь привел меня к сомнениям в прочнейшей из догм создания архитектуры приложений — MVC. И, когда я столкнулся с истинной силой реактивного и функционального программирования, я сосредоточился на простоте и уходе от раздувания, в создании которого наша отрасль так преуспела. Я думаю, вам могут быть интересны сделанные мной выводы.

Паттерн, который мы используем при разработке каждого экрана, MVC — Model-View-Controller. MVC был изобретен в те дни, когда Web еще не существовал и архитектура приложений была, в лучшем случае, толстым клиентом, который обращался напрямую к единственной базе данных по примитивной сети. И все же, спустя десятилетия, MVC до сих пор бессменно используется для создания Omni-Сhannel приложений.

В связи с предстоящим выходом Angular2, возможно, сейчас самое время для пересмотра использования паттерна MVC и, следовательно, той ценности, которую MVC фреймворки привносят в архитектуру приложений.

Впервые я столкнулся с MVC в 1990-м году, когда NeXT выпустил Interface Builder (здорово осознавать, что это ПО до сих пор актуально в наши дни). В то время Interface Builder и MVC представлялись как большой шаг вперед. В конце 90-х паттерн MVC был приспособлен к работе через HTTP (помните Struts?) и теперь MVC это краеугольный камень в архитектуре любых приложений, на все случаи жизни.

Даже React.js, казалось бы, далеко ушедший от догмы MVC, использовал этот эвфемизм, когда они представляли свой фреймворк: “React это лишь View в MVC”.

В прошлом году, когда я начал использовать React, я чувствовал что это что-то совершенно иное — вы где-то изменяете часть данных и, в тот же момент, без явного взаимодействия View и Model, весь UI изменяется (не только значения в полях и таблицах). Из-за этого я так быстро разочаровался в модели разработки React, и, очевидно, я был не одинок. Я поделюсь мнением Андре Медейроса:

React разочаровал меня по нескольким причинам. В основном из-за плохо спроектированного API, которое вынуждает пользователя [..] смешивать в одном компоненте несколько concerns.

Как проектировщик серверного API, я пришел к выводу, что не существует хорошего способа добавить вызовы API во front-end реализованный на React, именно потому, что React сосредоточен только на View, и в его модели разработки вообще нет понятия Controller.

Facebook до настоящего момента сопротивляется исправлению этого пробела на уровне фреймворка. Команда React разработала паттерн Flux, который так же разочаровывает, и теперь Dan Abramov продвигает еще один паттерн, Redux, который движется, в целом, в правильном направлении, но — я продемонстрирую это далее — не обеспечивает надлежащего способа работы с API из front-end.

Вы можете подумать, что, разработав GWT, Android SDK и Angular, инженеры Google имеют четкое представление (на английском языке звучит как каламбур — strong view) о том, какова наилучшая архитектура для front-end. Но, если вы почитаете некоторые соображения об архитектуре Angular2, вы не обязательно испытаете теплое чувство, что, уж хотя бы в Google, люди понимают, что они делают:

Angular 1 не был построен на идее компонентов. Вместо этого мы прикрепляем контроллеры к различным [элементам] страницы по нашему усмотрению. Области видимости присоединялись или растекались (flow through) в зависимости от того, как наши директивы инкапсулируют сами себя (изолированные scope, кто-нибудь?)

Выглядит ли построенный на компонентах Angular2 намного проще? Не совсем. Основной пакет Angular2 сам по себе содержит 180 определений, а весь фреймворк доходит до ошеломляющие почти 500 определений, и это все поверх HTML5 и CSS3. У кого есть время изучить и совершенствоваться в такого рода фреймворке для построения web-приложений? Что будет, когда выйдет Angular3?

Поработав с React и увидев, что представляет из себя Angular2, я впал в уныние — эти фреймворки методично вынуждают меня использовать паттерн BFF Screen Scraping, в котором каждое серверное API подгоняется под набор данных, необходимых на экране, до мелочей.

Это был мой момент “Да пошло все к черту”. Я буду просто создавать приложения, без React, без Angular, без всяких MVC-фреймворков, и посмотрю, возможно мне удастся найти более удачный способ соединить View и нижележащее API.

Что мне действительно понравилось в React, так это взаимодействие между Model и View. То, что React не основан на шаблонах и что View сам по себе не может обратиться за данными, чувствовалось как разумное направление для изучения (вы можете только передать данные во View).

Достаточно поработав с React вы понимаете, что его единственное назначение — декомпозиция View на набор чистых (pure) функций и JSX-разметку:

<V params={M}/>

Это не что иное как:

V = f(M)

К примеру, web-сайт одного из проектов, над которым я сейчас работаю, Gliiph, построен при помощи функций подобных этой:

Рис.1 функция, отвечающая за генерацию HTML для компонента слайдера.

Эта функция наполняется из модели:

Рис. 2. Модель, работающая со слайдерами.

Когда вы понимаете, что обычные JavaScript-функции могут прекрасно выполнить нужную работу, вашим следующим вопросом будет: “зачем вообще я должен использовать React?”.

Virtual dom? Если вам кажется, что вам он нужен (и я не уверен, что для многих это так), то есть варианты, и я думаю, что будут разработаны и другие.

GraphQL? Вообще-то нет. Не обманывайтесь доводами, что если Facebook использует это повсеместно, то это подойдет вам. GraphQL это не более чем декларативный способ создания View Model. Когда вы вынуждены формировать Model в соответствии с View это проблема, а не решение. Как вообще команда React (в том смысле, что он reactive) может полагать, что это нормально, запрашивать данные при помощи Client Specified Queries:

GraphQL полностью управляется требованиями View и front-end разработчиками, которые их написали [...] С другой стороны, GraphQL-запрос возвращает в точности то, что запрошено клиентской стороной и не более

Что команда GraphQL, кажется, упускает — маленькое изменение, которое скрывается JSX-синтаксисом — что функции изолируют Model от View. В отличии от шаблонов или “запросов, написанных front-end разработчиками” функции не требуют, чтобы Model подходил ко View.

Когда View создается при помощи функции (в противовес шаблону или запросу) вы можете преобразовать Model так, как вам нужно, и наилучшим образом реализовать View без добавления искусственных ограничений в Model.

К примеру, если View отображает значение v и графический индикатор, показывающий, является ли это значение отличным, хорошим или плохим, вам не нужно добавлять значение индикатора в Model — функция должна просто посчитать значение индикатора из значения v, которое предоставил Model.

На данный момент, это не особо хорошая идея, напрямую встраивать подобные вычисления во view. Но совсем не трудно так же сделать view-Model чистой функцией, и, следовательно, нет необходимости использовать GraphQL когда вам нужен четко сформулированный ViewModel:

V = f( vm(M) )

Как ветеран MDE (Model-driven engineering — прим. переводчика), я могу заверить вас, что писать код бесконечно лучше, чем метаданные, будь то шаблон или сложный язык запросов наподобие GraphQL.

Подобный функциональный подход имеет несколько важных преимуществ. Во-первых, так же как React, он позволяет вам декомпозировать ваши View на компоненты. Естественный интерфейс, который они создают, позволяет вам реализовать темы для вашего web-приложения или web-сайта или выполнить рендеринг View при помощи других технологий (нативных, к примеру). Также, реализация при помощи функций может усовершенствовать способы реализации responsive-дизайна, которые мы используем.

Я не удивлюсь, к примеру, если в ближайшие несколько месяцев разработчики начнут создавать темы для HTML5 реализованные как компоненты на основе JavaScript-функций. На данный момент это то, как я делаю все мои web-сайты. Я беру шаблон и сразу же оборачиваю его JavaScript-функциями. Я больше не использую Wordpress — я могу получить лучшее от технологий HTML5 и CSS3 с тем же уровнем затрат (или меньшим).

Также, такой подход призывает к новому способу взаимодействия между дизайнерами и разработчиками. Кто угодно может написать подобные JavaScript-функции, тем более дизайнер шаблонов. Здесь нет “binding” синтаксиса, который необходимо изучать, нет JSX, нет шаблонов Angular, только простые JavaScript-функции.

Что интересно, с точки зрения reactive data flow, эти функции могут работать там, где это имеет больше смысла — на сервере или на клиенте.

Но, что наиболее важно, данный подход позволяет View декларировать минимальный контракт взаимодействия с Model и оставляет Model-у решать, каким образом лучше всего предоставит нужные данные View. Такие вопросы как caching, lazy loading, orchestration, consistency под полным контролем Model. В отличие от шаблонов или GraphQL, никогда не возникает необходимость делать прямой запрос, составленный с точки зрения View.

Теперь, когда у нас есть способ отвязать друг от друга Model и View, следующий вопрос в том, как создать полновесную модель приложения из этого? Как должен выглядеть “Controller”? Для ответа на этот вопрос, давайте вернемся к MVC.

Apple знает кое что об MVC, так как они “украли” этот паттерн из Xerox SPARC в начале 80-х и с того момента религиозно следуют ему:

Рис. 3. Паттерн MVC.

Ключевой вопрос здесь в том, и Андре Медейрос очень красноречиво объяснил это, что паттерн MVC “интерактивный” (в противоположность реактивному). В традиционном MVC Action (Controller) вызывает метод обновления у Model и в случае успеха (или ошибки) решает, каким образом обновить View. Как он (Андре Медейрос — прим. переводчика) замечает, Controller не обязан действовать именно таким образом. Есть другой, не менее разумный, reactive, способ, смысл которого заключается в том, что Action должен просто передавать значения в Model, независимо от результата, вместо того, чтобы принимать решение о том, как должен быть обновлен Model.

Ключевым вопросом тогда становится: “как вы интегрируете Action-ы в reactive flow?” Если вы хотите разбираться в том, что такое Action-ы, вам может захотеться взглянуть на TLA+. TLA расшифровывается как “Temporal Logic of Actions”, формулировка изобретенная доктором Лампортом, получившим премию Тьюринга за это. Согласно TLA+ Action-ы это чистые функции:

 data’ = A (data)

Мне очень нравится основная идея TLA+, поскольку она подтверждает тот факт, что функции это лишь преобразования заданного набора данных.

С учетом этого, реактивный MVC может выглядеть примерно как:

V = f( M.present( A(data) ) ) 

Данное выражение ставит условием что Action, когда он срабатывает, высчитывает набор данных из набора входных параметров (таких как пользовательский ввод), которые передаются в Model, который, в свою очередь, решает, когда и как себя обновить. Когда обновление выполнено, View рендерится из нового состояния Model. Реактивная петля замыкается. Способ, которым Model сохраняет и извлекает данные, не имеет отношения к reactive flow, и никогда, абсолютно никогда, не должен быть “написан front-end разработчиками”. Никаких оправданий.

Еще раз, Action это чистые функции, без состояния и без side effect-ов (из уважения к Model, исключаем logging, к примеру).

Реактивный паттерн MVC интересен, поскольку, за исключением Model (разумеется), все остальное это чистые функции. Говоря по совести, Redux реализует именно это паттерн, но с ненужными церемониями в отношении React и несколько избыточной связанностью между Model и Action-ами внутри reducer. Интерфейс между Action-ами и Model это лишь передача сообщений.

Исходя из вышесказанного, паттерн Reactive MVC, в том виде как он есть, не завершен. Он не масштабируется под реальные приложения как Дэн любит утверждать. Давайте рассмотрим простой пример, объясняющий почему.

Предположим, нам необходимо реализовать приложение, которое управляет пусковой установкой для ракет: как только мы начали отчет, система убавляет счетчик и, когда он достигает нуля, если все свойства Model имеют корректные значения, инициируется запуск ракеты.

Данное приложение имеет простую машину состояний:

Рис. 4. Машина состояний приложения для запуска ракет.

Как уменьшение (decrement), так и запуск (launch), являются “автоматическими” действиями. То есть каждый раз, когда мы вносим (или вносим повторно) состояние отсчета, условия перехода будут оценены и, если состояние счетчика больше нуля, будет выполняться действие decrement. А когда значение достигнет нуля — будет вызвано действие launch. Действие отмена (abort) может быть вызвано в любой момент, что приведет систему в отмененное состояние.

В MVC такая логика будет реализована в Controller, и, вероятно, вызываться по таймеру из View.

Этот параграф очень важен, поэтому прочтите его внимательно. Мы увидели, что в TLA+ Action не имеет side effects-ов и результирующее состояние вычисляется как только Model обрабатывает результат вызова Action и обновляет сам себя. Это существенное отступление от традиционной семантики машин состояний, где Action определяет результирующее состояние. Иными словами, результирующее состояние не зависит от Модели. В TLA+, Action-ы, которые разрешены, и, следовательно, доступны для вызова в state representation (то есть во View) не связаны напрямую с Action-ами, которые вызывают изменения состояния. Другими словами, машины состояния не должны быть кортежами, соединяющими два состояния (S1, A, S2) каковыми они обычно являются. Они являются, скорее, кортежами форм (Sk, Ak1, Ak2,...) которые определяют все разрешенные Actions для состояния Sk с результирующим состоянием вычисляемым после того, как Action был применен к системе и Model обработал изменения.

Семантика TLA+ предоставляет превосходный способ концептуализации системы, при котором вы представляете объект “состояние”, отделенный от Action и View (которые являются лишь отображением состояния).

Model в нашем приложении выглядит следующим образом:

model = {
counter:,
started:,
aborted:,
launched:
}

Четыре (управляющих) состояния системы ассоциированы со следующими значениями в Model:

ready = {counter: 10, started: false, aborted: false, launched: false }
counting = {counter: [0..10], started: true, aborted: false, launched: false }
launched = {counter: 0, started: true, aborted: false, launched: true}
aborted = {counter: [0..10], started: true, aborted: true, launched: false}

Model описывается свойствами системы и их возможными значениями, в то время как cостояние определяет Action-ы, доступные для заданного набора значений. Бизнес-логика подобного вида должна быть где-то реализована. Мы не можем ожидать, что пользователю можно доверить выбор, какие действия возможны, а какие нет. Это условие, которое невозможно обойти. Тем не менее, подобную бизнес-логику сложно писать, отлаживать и сопровождать, особенно когда вам недоступна семантика для ее описания, например, в MVC.

Давайте напишем немного кода для нашего примера с запуском ракеты. С точки зрения TLA+, next-action предикат логически определяется из отображаемого состояния. Как только текущее состояние представлено, следующим шагом будет выполнение next-action предиката, который вычисляет и выполняет следующий Action, если таковой имеется. Оно же, в свою очередь предоставит данные Model, который инициирует рендеринг нового state representation и так далее.

Рис. 5. Реализация приложения для запуска ракет.

Обратите внимание, что в случае клиент-серверной архитектуры нам придется использовать протокол наподобие WebSocket (или polling, если WebSocket недоступен) для корректного отображения состояния после того, как автоматический Action выполнится.

Я написал очень маленькую open source библиотеку на Java и JavaScript, которая строит состояние объекта с верной, с точки зрения TLA+, семантикой и привел примеры, которые используют WebSocket, Polling и Queueing для реализации клиент-серверного взаимодействия. Как вы видите по примеру с приложением для запуска ракет, вы не обязаны использовать эту библиотеку. Реализация состояния достаточно проста в написании когда вы понимаете, что нужно написать.

Я считаю, что теперь у нас есть все элементы для того, чтобы формально описать новый шаблон, как альтернативу MVC — SAM pattern (State-Action-Model), реактивный, функциональный паттерн, уходящий корнями к React.js и TLA+.

Паттерн SAM может быть описан в виде следующего выражения:

 V = S( vm( M.present( A(data) ) ), nap(M))

которое ставит условием, что View V системы может быть вычислено как чистая функция от Model, после применения Action-а A.

В SAM, A (Actions), vm (ViewModel), nap (next-action predicate) и S (state representation) являются и должны являться чистыми функциями. В случае SAM, то, что мы обычно называем “Состояние” (значения свойств системы) полностью ограничивают Model и логика, которая изменяет эти значения, недоступна за пределами Model.

В качестве примечания, предикат next-action, или nap() это callback, вызываемый как только state representation был создан и его предстоит отрендерить пользователю.

Рис. 6. Паттерн State-Action-Model (SAM).

Паттерн как таковой не зависит от каких-либо протоколов (и может быть с легкостью реализован через HTTP) и каких-либо клиентских/серверных технологий.

SAM не подразумевает, что вы всегда должны использовать семантику машины состояний дабы получить содержимое View. Когда вызов Action выполняется только из View, next-action предикат это null-функция. Хотя, это может быть хорошей привычкой — четко выделять управляющие состояния нижележащей машины состояний, поскольку View может выглядеть по разному в зависимости от того или иного (управляющего) состояния.

С другой стороны, если ваша машина состояний включает автоматические Action-ы, ни ваши Action-ы, ни ваш Model не будут чистыми без next-action предиката: либо некоторые Action-ы станут stateful, либо Model будет вызывать Action-ы, что не входит в ее задачи. Между прочим, и это неожиданно, объект состояния не содержит какое-либо “состояние”, это тоже чистая функция, которая рендерит View и вычисляет next-action предикат, делая и то и другое на основе значений свойств Model.

Ключевое преимущество это нового паттерна в том, что он четко отделяет CRUD операции от Action-ов. Model сам отвечает за свой persistence, который будет реализован при помощи CRUD операций, недоступных из View. В частности, View никогда не будет находиться в положении для “извлечения” данных. Единственное, что View может делать это запрашивать текущий state representation системы и инициировать reactive flow за счет вызова действий.

Action-ы представляют собой всего лишь канал для внесения изменений в Model. Они, сами по себе, не имеют side effect-а (для Model). Когда необходимо, Action-ы могут вызывать сторонние API (еще раз, без side effect для Model). Например, действие по изменению адреса может вызвать сервис для его проверки и передать в Model адрес, возвращенный данным сервисом.

Вот как действие “Смена Адреса”, вызывающее API для проверки адреса, будет реализовано:

Рис. 7. Реализация действия “Смена Адреса”

Составные элементы паттерна, Action-ы и Model-ы, могут быть составлены (composed) свободно:

Композиция на основе функций:

data’ = A(B(data))

Одноуровневая композиция (один и тот же набор данных передается двум моделям):

M1.present(data’)
M2.present(data’)

Композиция “Родительский-дочерний” (родительский Model управляет набором данных, передаваемым дочернему):

M1.present(data’,M2)
function present(data, child) {
                // perform updates
                …
                // synch models
                child.present(c(data))
}

Композиция посредством Publish/Subscribe:

M1.on(“topic”, present )
M2.on(“topic”, present )

Или

M1.on(“data”, present )
M2.on(“data”, present )

Для архитекторов, которые мыслят в терминах Систем Записей и Систем Участия (прочитать что это такое можно здесь — прим. переводчика) данный паттерн помогает определить интерфейс между двумя слоями (рис. 8) с Model, отвечающим за все взаимодействия с Системой Записей.

Рис. 8. Модель композиции SAM.

Паттерн composable сам по себе и вы можете реализовать экземпляр SAM запускающийся в браузере для поддержки поведения в стиле wizard-ов (к примеру, ToDo application), взаимодействующий с экземпляром SAM на сервере:

Рис. 9. Композиция экземпляров SAM.

Пожалуйста, обратите внимание, что внутренний экземпляр SAM представлен как часть state representation, сгенерированного внешним экземпляром SAM.
Восстановление сессии должно предшествовать срабатыванию Action-a (рис. 10). SAM делает возможной интересную композицию, когда View может вызывать сторонний Action, предоставляющее токен и callback, указывающий на Action системы, который авторизует и верифицирует вызов, перед тем как предоставлять данные для Model.

Рис. 10. Управление сессиями в SAM.

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

{ _name : ‘/^[a]$/i’ } // Names that start with A or a
{ _customerId: ‘123’ } // customer with id = 123

Model может выполнять необходимые операции для сопоставления с запросом, обновлять свое содержимое и инициировать рендеринг View. Схожий набор конвенций может быть использован для создания, обновления или удаления элементов Model. Есть целый ряд способов которые могут быть реализованы для передачи результата работы Action-ов в Model (data sets, events, actions). У каждого подхода есть свои достоинства и недостатки и, в конечном счете, подход может определяться исходя из предпочтений. Я предпочитаю подход с использованием data sets.

С точки зрения исключений (exceptions), так же как и в React, ожидается, что Model будет содержать информацию о соответствующем исключении как значения свойств (будь то исключение от Action или возвращенное CRUD-операцией). Данные значения будут использованы при рендере state representation чтобы отобразить исключение.

С точки зрения кэширования, SAM позволяет выполнять его на уровне state representation. Ожидаемо, кэширование результатов этих функций state representation должно привести к более высокому hit rate, раз мы теперь инициируем кэширование на уровне компонента/состояния вместо уровня Action/Response.

Реактивная и функциональная структура паттерна делает легким воспроизведение и unit-тестирование.

Паттерн SAM полностью меняет парадигму front-end архитектуры, поскольку, основываясь на TLA+, бизнес-логика может быть четко разделена на:

• Action-ы как чистые функции
• CRUD-операции в Model
• Состояния, которые управляют автоматическими Action-ами

С моей точки зрения, как разработчика API, паттерн сдвигает ответственность за проектирование API обратно на сервер, с минимально возможным контрактом между View и Model.

Action-ы, как чистые функции, могут быть повторно использованы между моделями если Model принимает возвращаемый результат от Action. Мы можем ожидать, что библиотеки Action-ов, темы (state representation) и, возможно, библиотеки Model-ов будут расцветать, раз они теперь композируются независимо.

С SAM микросервисы естественным образом помещаются за Model. Фреймворки наподобие Hivepod.io могут быть подключены на этом уровне, по-большому счету, as-is.

Что наиболее важно, данный паттерн, подобно React, не требует какого-либо data binding или шаблонов.

Я ожидаю, что со временем SAM поспособствует тому, что virtual-dom будет повсеместно реализован в браузерах и новые state representation будут напрямую обрабатываться через соответствующее API.

Я нахожу данное исследование преобразующим: времена существовавшего десятилетия подхода Object Orientation похоже, почти прошли. Я не могу больше мыслить в терминах иных чем реактивный или функциональный. Те вещи, которые я реализовал с помощью SAM и скорость, с которой я могу их реализовать, беспрецендентны. И еще один момент. Я теперь могу сосредоточиться на проектировании API и сервисов, которые не следуют паттерну “screen scrapping”.

Я хочу поблагодарить и выразить признательность людям, которые любезно согласились проверить эту статью: Prof. Jean Bezivin, Prof. Joëlle Coutaz, Braulio Diez, Adron Hall, Edwin Khodabackchian, Guillaume Laforge, Pedro Molina, Arnon Rotem-Gal-Oz.

Об авторе:
Жан-Жак Дюбре является основателем xgen.io и gliiph. Он занимается созданием Service Oriented Architectures и платформ API последние 15 лет. Является бывшим членом исследовательской команды в HRL и получил докторскую степень в University of Provence (Luminy campus) (ныне Aix-Marseille University — прим. переводчика), доме языка Prolog. Изобретатель методологии BOLT.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Android VIPER на реактивной тяге

Чем больше строк кода написано, тем реже хочется дублировать код, а чем больше проектов реализовано, тем чаще обходишь старые, хоть и зачастую любимые, грабли, и начинаешь все больше интересоваться архитектурными решениями.
Думаю, достаточно не привычно рядом с Android встретить горячо любимый iOS-разработчиками архитектурный шаблон VIPER, мы тоже первое время пропускали мимо ушей разговоры из соседнего отдела по этому поводу, пока вдруг не обнаружили, что стали невольно использовать такой шаблон в своих Android приложениях.

Как такое могло произойти? Да очень просто. Поиски изящных архитектурных решений начались еще за долго до Android приложений, и одним из моих любимых и незаменимых правил всегда было — разделение проекта на три слабосвязанных слоя: Data, Domain, Presentation. И вот, в очередной раз изучая просторы Интернета на предмет новых веяний в архитектурных шаблонах для Android приложений, я наткнулась на великолепное решение: Android Clean Architecture, здесь, по моему скромному мнению, было все прекрасно: разбиение на любимые слои, Dependency Injection, реализация presentation layer как MVP, знакомый и часто используемый для data layer шаблон Repository.

Но помимо давно любимых и знакомых приемов в проектировании было место и открытиям. Именно этот проект познакомил меня с понятием Interactor (объект содержащий бизнес логику для работы с одной или несколькими сущностями), а так же именно здесь мне открылась мощь реактивного программирования.

Реактивное программирование и в частности rxJava достаточно популярная тема докладов и статей за прошедший год, поэтому вы без труда сможете ознакомится с этой технологией (если конечно, вы еще с ней не знакомы), а мы продолжим историю о VIPER.

Знакомство с Android Clean Architecture привело к тому, что любой новый проект, а так же рефакторинг уже существующих сводился к трехслойности, rxJava и MVP, а в качестве domain layer стали использоваться Interactors. Оставался открытым вопрос о правильной реализации переходов между экранами и здесь все чаще стало звучать понятие Router. Сначала Router был одинок и жил в главной Activity, но потом в приложении появились новые экраны и Router стал очень громоздким, а потом появилась еще одна Activity со своими Fragments и тут пришлось подумать о навигации всерьез. Вся основная логика, в том числе переключение между экранами, содержится в Presenter, соответственно Presenter-у необходимо знать о Router, который в свою очередь должен иметь доступ к Activity для переключения между экранами, таким образом Router должен быть для каждой Activity свой и передаваться в Presenter при создании.

И вот как-то в очередной раз глядя на проект пришло понимание, что у нас получился V.I.P.E.R — View, Interactor, Presenter, Entity and Router.

Думаю, вы заметили на схеме Observable, – именно здесь скрывается вся мощь реактивной тяги. Слой данных не просто извлекает из удаленного или локального хранилища данные в необходимом для нас представлении, он передает в Interactor всю последовательность действий завернутую в Observable, который в свою очередь может продолжить эту последовательность по своему усмотрению исходя из реализуемой задачи.

А сейчас разберем небольшой пример реализации VIPER для Android (исходники):
Предположим, что перед нами стоит задача разработать приложение, которое раз в три секунды запрашивает у “не очень гибкого” сервера список сообщений и отображает последнее для каждого отправителя, а так же оповещает пользователя о появлении новых. По тапу на последнее сообщение появляется список всех сообщений для выбранного отправителя, но сообщения все так же продолжают раз в 3 секунды синхронизироваться с сервером. Так же из главного экрана мы можем попасть в список контактов, и просмотреть все сообщения для одного из них.

И так, приступим, у нас есть три экрана: чаты (последние сообщения от каждого контакта), список сообщений от конкретного контакта и список контактов. Накидаем схему классов:

Экранами являются фрагменты, переходы между которыми регулируются Activity, реализующей интерфейс Router. Каждый фрагмент имеет свой Presenter и реализует необходимый для взаимодействия с ним интерфейс. Для облегчения создания нового Presenter и фрагмента, были созданы базовые абстрактные классы: BasePresenter и BaseFragment.

BasePresenter — содержит ссылки на интерфейс View и Router, а так же имеет два абстрактных метода onStart и onStop, повторяющих жизненный цикл фрагмента.

public abstract class BasePresenter<View, Router> {
   private View view;
   private Router router;

   public abstract void onStart();

   public abstract void onStop();

   public View getView() {
       return view;
   }

   public void setView(View view) {
       this.view = view;
   }

   public Router getRouter() {
       return router;
   }

   public void setRouter(Router router) {
       this.router = router;
   }
}

BaseFragment — осуществляет основную работу с BasePresenter: инициализирует и передает интерфейс взаимодействия в onActivityCreated, вызывает в соответствующих методах onStart и onStop.

Любое Android приложение начинается с Activity, у нас будет только одно MainAcivity в котором переключаются фрагменты.

Как уже было сказано выше Router живет в Activity, в конкретном примере MainActivity просто реализует его интерфейс, соответственно для каждой Activity свой Router, который управляет навигацией между фрагментами внутри нее, следовательно каждый фрагмент в такой Activity должен иметь Presenter, использующий один и тот же Router: так и появился BaseMainPresenter, который должен наследовать каждый Presenter работающий в MainActivity.

public abstract class BaseMainPresenter<View extends BaseMainView> 
                                                          extends BasePresenter<View, MainRouter> {
}

При смене фрагментов в MainActivity меняется состояние Toolbar и FloatingActionButton, поэтому каждый фрагмент должен уметь сообщать необходимые ему параметры состояния в Activity. Для реализации такого интерфейса взаимодействия используется BaseMainFragment:

public abstract class BaseMainFragment extends BaseFragment implements BaseMainView {

 public abstract String getTitle(); //заголовок в Toolbar

  @DrawableRes
 public abstract int getFabButtonIcon();  //иконка FloatingActionButton

//событие по клику на FloatingActionButton
 public abstract View.OnClickListener getFabButtonAction(); 

@Override
public void onActivityCreated(Bundle savedInstanceState) {
   super.onActivityCreated(savedInstanceState);
   MainActivity mainActivity = (MainActivity) getActivity();

//Передаем презентеру роутер
   getPresenter().setRouter(mainActivity);

//Сообщаем MainActivity что необходимо обновить Toolbar и FloatingActionButton
   mainActivity.resolveToolbar(this);
   mainActivity.resolveFab(this);
}

@Override
public void onDestroyView() {
   super.onDestroyView();

//Очищаем роутер у презентера
   getPresenter().setRouter(null);
}
   ….
}

BaseMainView — еще одна базовая сущность для создания фрагментов в MainActivity, это интерфейс взаимодействия, о котором знает каждый Presenter в MainActivity. BaseMainView позволяет отображать сообщение об ошибке и отображать оповещения, этот интерфейс реализует BaseMainFragment:

...
@Override
public void showError(@StringRes int message) {
   Toast.makeText(getContext(), getString(message), Toast.LENGTH_LONG).show();
}

@Override
public void showNewMessagesNotification() {
   Snackbar.make(getView(), R.string.new_message_comming, Snackbar.LENGTH_LONG).show();
}
...

Имея заготовки в виде таких базовых классов значительно ускоряется процесс создания новых фрагментов для MainActivity.

Router
А вот какой получился MainRouter:

public interface MainRouter {

   void showMessages(Contact contact);

   void openContacts();

}

Interactor
Каждый Presenter использует один или несколько Interactor для работы с данными. Interactor имеет лишь два публичных метода execute и unsubscribe, то есть Interactor можно запустить на исполнение и отписаться от запущенного процесса:

public abstract class Interactor<ResultType, ParameterType> {

   private final CompositeSubscription subscription = new CompositeSubscription();
   protected final Scheduler jobScheduler;
   private final Scheduler uiScheduler;

   public Interactor(Scheduler jobScheduler, Scheduler uiScheduler) {
       this.jobScheduler = jobScheduler;
       this.uiScheduler = uiScheduler;
   }

   protected abstract Observable<ResultType> buildObservable(ParameterType parameter);

   public void execute(ParameterType parameter, Subscriber<ResultType> subscriber) {
       subscription.add(buildObservable(parameter)
               .subscribeOn(jobScheduler)
               .observeOn(uiScheduler)
               .subscribe(subscriber));
   }

   public void unsubscribe() {
           subscription.clear();
   }
}

Entity
Для доступа к данным Interactor использует один или несколько DataProvider и формирует rx.Observable для последующего исполнения.

Постановка задачи для рассматриваемого примера включала в себя необходимость осуществления периодического запроса к серверу, что без труда удалось реализовать при помощи RX:

public static long PERIOD_UPDATE_IN_SECOND = 3;

@Override
public Observable<List<Message>> getAllMessages(Scheduler scheduler) {
   return Observable
                        .interval(0, PERIOD_UPDATE_IN_SECOND, TimeUnit.SECONDS, scheduler)
                        .flatMap(this::getMessages);
}

Приведенный выше пример кода каждые три секунды выполняет запрос на получения списка сообщений и отправляет оповещение подписчику.

Заключение
Архитектура — скелет приложения, и если забыть о ней можно в итоге получить урода. Четкое разделение ответственности между слоями и типами классов облегчает поддержку, тестирование, ввод нового человека на проект занимает меньше времени и настраивает на единообразный стиль в программировании. Базовые классы помогают избежать дублирования кода, а rx не думать об асинхронности. Идеальная архитектура как и идеальный код величины практически не достижимые, но стремиться к ним — значит профессионально расти.

P.S. Есть идеи продолжить цикл статей, рассказав подробнее об интересных случаях в реализации:
presentation layer — сохранение состояния во фрагменте, композитные view;
domain layer — Interactor для нескольких подписчиков;
data layer — организация кэширования.
Если заинтересовало, ставьте плюсик :)

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.