• Что нужно знать про арифметику с плавающей запятой



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

    Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.
    Читать дальше →
  • Lock-free структуры данных. Основы: Модель памяти


      В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

      В этой статье мы рассмотрим модель памяти C++11.
      Читать дальше →
      • +66
      • 72.1k
      • 8
    • Кадры решают всё или о биче современных компаний

        image
        Хотелось бы немного рассказать о тех ошибках, которые очень опасно совершать особенно сейчас, особенно в странах или городах золотого миллиарда. Думаю каждый работающий или сталкивающийся с деятельностью большой или не очень компании (или гос структуры) как и я удивляется на сколько же всё не эффективно и поражается как при таком раздолбайстве и пофигизме шестерёнок машина всё еще работает.
        Читать дальше →
      • Зачем Win32-приложению манифест?

        Недавно на руборде в разделе Программирование был задан вопрос: «Зачем Win32-приложению манифест? На что он влияет?». Первое, что сразу приходит в голову большинству программистов — это темы оформления. Но на самом деле в современных виндах манифест нужен не только для этого. Я подумал и написал пять ключевых аспектов, на которые влияет манифест или его отсутствие. После этого сразу несколько человек попросили оформить этот пост в виде более развернутой статьи.
        Мое исследование темы манифестов под катом
      • Шпаргалка по HTTP-библиотекам для С++

        • Tutorial
        К сожалению, в стандартной библиотеке языка С++ нет никаких средств для работы с протоколом HTTP. Возможно, в будущем появятся, но на данный момент каждый раз при необходимости дёрнуть какой-нибудь REST-сервис, пропарсить веб-страничку, написать простенького бота или краулера приходится задаваться вопросами «А какую же библиотеку взять, так чтобы побыстрее и попроще?». Иногда проект уже использует какой-то фреймворк (а иногда даже несколько) и тогда приходится вспоминать «А как же сделать HTTP-запрос имеющимися средствами?». Чтобы не путаться я решил написать для себя шпаргалку с примерами HTTP-запросов на С++ с применением разных библиотек. А самое удобное место для хранения подобных шпаргалок — Хабр: и сам не потеряешь, и другим может пригодиться.

        Будут рассмотрены:
        • WinInet
        • WinHttp
        • Casablanca
        • Qt
        • POCO
        • wxWidgets
        • Boost.Asio
        • libcurl
        • neon
        • .NET (С++/CLI)
        • IXMLHTTPRequest
        • HappyHttp
        • cpp-netlib


        Читать дальше →
      • Два простых правила для предотвращения взаимных блокировок на мьютексах

          Здравствуйте, уважаемые Хабраюзеры!

          Так сложилось, что это третий пост в блоге нашей компании, и, как и первые два, он посвящен вопросам многопоточного программирования и проблемам, которые при этом возникают. Получилось так неслучайно, ведь мы на собственной «шкуре» испытали, что ситуации, возникающие при написании многопоточных программ, невероятно сложны для отладки, так как во многом определяются динамикой работы программы на конкретной аппаратной платформе. Уверен, что большинство программистов сталкивались с ситуацией, когда программа, которая прекрасно работает на одном компьютере, на другом совершенно неожиданно начинает дедлочиться практически «на ровном месте».
          Читать дальше →
        • Blind Deconvolution — автоматическое восстановление смазанных изображений

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


            В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
            Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
            В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
            Внимание, под катом много картинок!
            Читать дальше →
          • Заметки для построения эффективных Django-ORM запросов в нагруженных проектах

              Написано, т.к. возник очередной холивар в комментариях на тему SQL vs ORM в High-Load Project (HL)

              Преамбула


              В заметке Вы сможете найти, местами, банальные вещи. Большая часть из них доступна в документации, но человек современный часто любит хватать все поверхностно. Да и у многих просто не было возможности опробовать себя в HL проектах.
              Читая статью, помните:
              • Никогда нельзя реализовать HL-проект на основе только одной манипуляции с ORM
              • Никогда не складывайте сложные вещи на плечи БД. Она нужна Вам чтобы хранить инфу, а не считать факториалы!
              • Если вы не можете реализовать интересующую Вас идею простыми средствами ORM — не используйте ORM для прямого решения задачи. И тем более не лезте в более низкий уровень, костыли сломаете. Найдите более элегантное решение.
              • Извините за издевательски-юмористический тон статьи. По другому скучно :)
              • Вся информация взята по мотивам Django версии 1.3.4
              • Будьте проще!

              И-и-и да, в статье будут показаны ошибки понимания ORM, с которыми я столкнулся за три с лишним года работы с Django.
              Читать дальше →
            • Частые ошибки при разработке lockfree-алгоритмов и их решения

                На хабре уже было несколько статей про lock-free алгоритмы. Этот пост — это перевод статьи моего коллеги, которую мы планируем публиковать в нашем корпоративном блоге. По роду деятельности мы пишем огромное количество lock-free алгоритмов и структур данных, и этой статьей хочется показать, насколько это интересно и сложно одновременно.



                Эта статья во многом похожа на эту статью, но в той статье рассматриваются не все проблемы, с которыми можно столкнуться, разрабатывая lock-free структуры данных, и уделяется очень мало внимания решению этих проблем. В этой статье хочется детально остановиться на некоторых решениях, которые мы используем в реальной реализации lock-free структур данных в нашем продукте, и больше внимания уделить оценке производительности.
                Читать дальше →
              • Как запустить программу без операционной системы


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

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

                  Итак, цель: затратив как можно меньше усилий, создать собственную загрузочную флешку, которая всего-навсего печатает на экране компьютера классический “Hello World”.

                  Читать дальше →
                • Об одном методе распределения памяти

                  • Tutorial
                  image
                  Не секрет, что иногда выделение памяти требует отдельных решений. Например — когда память выделяется и освобождается стремительным домкратом потоком, в параллельных задачах.

                  В результате стандартный консервативный аллокатор выстраивает все запросы в очередь на pthread_mutex / critical section. И наш многоядерный процессор медленно и печально едет на первой передаче.

                  И что с этим делать? Познакомимся поближе с деталями реализации метода Scalable Lock-Free Dynamic Memory Allocation. Maged M. Michael. IBM Thomas J. Watson Research Center.

                  Самый простой код что я сумел найти — написан под LGPL камрадами Scott Schneider и Christos Antonopoulos. Его и рассмотрим.

                  Читать дальше →
                • Подборка цветовых схем подсветки синтаксиса для Sublime, TextMate и Vim

                    Дейл Риз — один из разработчиков PHP-фреймворка Laravel — выложил на Гитхаб весьма приятную подборку цветовых схем, совместимую с Sublime Text 2, Vim и TextMate. В неё входят преимущественно тёмные темы (21 из 25), и, что бывает не так уж часто, практически все они выглядят очень прилично — есть из чего выбрать. Инструкции по установке и скриншоты каждой темы — в репозитории.
                    Под катом — скриншоты всех 25 схем.
                    Читать дальше →
                  • Ошейник для собаки-сияки

                      Введение

                      Итак, у меня есть собака.
                      Краткое резюме:
                      Кличка: Белка
                      Окрас: Белый с рыжим
                      Порода: Западносибирская лайка с кем-то еще
                      Происхождение: Дворянское
                      Стоимость: 0р 0к

                      Собака была приобретена в собственном подъезде за еду и кров. Была выброшена какими-то негодяями без еды и воды в картонной коробке без фирменных логотипов породы и адреса завода-изготовителя. Ну да не важно, мы и с менее качественным товаром имели дело, а тут такая рыжая морда, и совсем бесплатно. Берем!
                      Пришлось принимать товар как есть, NO-NAME. Скорее всего, сделано в Китае. Гарантийные претензии тоже непонятно, кому предъявлять, а они были — в собаке водились глисты длиннее ее самой. К счастью, все это в прошлом. Зверюга подросла. Доказала свою преданность и послушность, за что получила возможность гулять без веревки на шее. Поскольку это не просто собака, а настоящая собака-гуляка, которая привыкла к полноценной четырёхразовой прогулке без поводка (она у меня совсем не агрессивная, но очень любознательная и послушная), ей потребовался своеобразный маячок, чтобы наблюдать ее похождения даже в темноте, и не нервничать, куда ж она подевалась. А подеваться ей есть куда — ее любимое занятие — приносить палки хозяину, и требовать, чтобы он ее кинул. Ну а найти-уж ее дело. Но это ж не простая собака, а собака, у которой папка — программист и немножко электронщик. Впрочем, даже простой ошейник с DealExtreme приковывает взгляды окружающих, особенно радуются дети. Разве это не стоит того? Но начнем с начала. Под катом много текста!
                      Читать дальше →
                    • Демонстрация сбоев программы при отсутствии барьеров памяти

                        Джефф Прешинг (Jeff Preshing) опубликовал отличную демонстрацию, как нормальный код C++ возвращает непредсказуемый результат на многоядерных процессорах со слабо упорядоченной обработкой очереди запросов (Weakly-Ordered CPU), то есть на ARM-процессорах. Например, на iPhone или каком-нибудь современном Android-устройстве.

                        Простая программа C++ с двумя потоками 20.000.000 раз прибавляет единичку к значению, защищённому мьютексом, — и каждый раз на выходе получается разный результат, который меньше 20.000.000!



                        Как говорится, наш враг — CPU.
                        Читать дальше →
                      • Мультиметоды в C++. Библиотечная реализация. Введение в MML

                          Наверное, многие C++-программисты слышали про мультиметоды и знают о том, что по сей день нет для этого языка приемлемой реализации: ни языковой поддержки, ни внешних библиотек. Есть кодогенераторы, выкрутасы через виртуальные методы, частный случай двойной диспетчеризации aka паттерн Посетитель (Visitor). Но ведь хочется просто реализовать несколько функций и указать: этот набор функций — есть мультиметод и точка.

                          О мультиметодах и некоторых подходах к их библиотечной реализации давно писали Мейерс и Александреску. Почти 20 лет эти идеи обсуждаются в различной литературе по C++, но до сих пор так и не были развиты до законченного решения, которое можно было бы удобно использовать в реальных проектах…

                          Я решил попытать счастья, дерзнуть, предложить свое видение этой проблемы и способ ее решения. Получилась шаблонная библиотека на одних только заголовочниках.
                          Это реализация под стандарт C++03, на чистом C++: без каких-либо кодогенераторов и дополнений. Цель — библиотека с простым и понятным интерфейсом для реализации возможности перегружать функций по типу (и даже по значению) во время выполнения (это была программа минимум, в конечном итоге получилось еще много вкусностей).
                          Далее под катом...
                        • Организация рабочих потоков: управление состоянием движка

                            Данная статья является продолжением статьи — Организация рабочих потоков: синхронизационный канал. Продолжение родилось как попытка написать пример использования подхода с синхронными сообщениями.

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

                            Давайте вернемся к примеру с предыдущей статьи. У нас есть графический интерфейс, отображающий состояние движка с рабочим потоком. Допустим движок можно запустить, остановить, поставить на паузу и соответственно снять с паузы. Для реализации такого поведения проще всего применить что-то подобное шаблонам проектирования конечный автомат и наблюдатель.
                            Читать дальше →
                          • Организация рабочих потоков: синхронизационный канал

                              Представьте себе архитектуру типичного приложения:

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

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

                              Казалось бы, как можно допустить ошибку в такой простой ситуации?
                              Читать дальше →
                            • Многопоточный Observer на С++ (практика)

                              Есть много вариаций на тему данного паттерна, но большинство примеров не подходит для многопоточных приложений.
                              В этой статье я хочу поделится опытом применения паттерна в многопоточных приложениях и опишу основные проблемы, с которыми мне приходилось сталкиваться.
                              Цель данной стати — обратить внимание разработчиков на проблемы, с которыми можно столкнуться при создании многопоточных приложений. Выявить подводные камни в реализации коммуникации между компонентами в многопоточном приложении.
                              Если Вам необходимо готовое решение, обратите внимание на библиотеку Signals2, котрая включена в boost с мая 2009-го года.
                              Я не пытаюсь предоставить решение, которое можно было бы использовать в готовом виде. Но тем не менее, ознакомившись с материалом, можно обойтись без использования сторонних библиотек, в тех проектах, в которых они по каким-либо причинам не доступны или нежелательны (драйвера, низкоуровневые приложения и т.п.).
                              Читать дальше →