Pull to refresh
  • by relevance
  • by date
  • by rating

Куча Хаскеля

Haskell *
Translation

Куча Хаскеля — довольно странное место. Она не похожа на кучу в традиционном языке со строгими вычислениями...

… которая представляет из себя кучу мусора из старых добрых простых данных!
Читать дальше →
Total votes 62: ↑54 and ↓8 +46
Views 1.4K
Comments 34

Вычисление в куче Хаскеля

Haskell *
Translation
Начало серии Куча Хаскеля

Дух новогодних подарков

Сегодня в статье мы кратко рассмотрим, что происходит, когда вы в куче Хаскеля открываете подарок с духом внутри. Почти во всём, что есть в куче, кроме констант и того, что уже вычислено, сидит дух. Весь вопрос в том, что станет делать дух в подарке.
Читать дальше →
Total votes 36: ↑29 and ↓7 +22
Views 1.2K
Comments 13

IO работает с кучей Хаскеля

Haskell *
Translation
Начало серии Куча Хаскеля
В этой статье мы сосредоточимся на вас. Вы всё крутитесь около кучи Хаскеля и норовите открыть подарок. В конце концов, подарки сами по себе не открываются.
Читать дальше →
Total votes 32: ↑25 and ↓7 +18
Views 1K
Comments 3

Опасности метода finalize

Java *
Во время написания статьи про использование фантомных ссылок, мне потребовалось сослаться на неудобства возникающие при работе с методом finalize. К тому же, считаю, что данный топик будет полезен всем начинающим java разработчикам, а некоторые пункты будет не лишним вспомнить и матерым программистам, ведь использовать метод finalize очень просто, чего не скажешь о поиске последсвий этого. Даже если вы твердо убеждены никогда не использовать метод finalize, это еще не значит, что ваши предыдущие коллеги их не использовали, и вам не надо понимать как они работают.
Читать дальше →
Total votes 33: ↑31 and ↓2 +29
Views 19K
Comments 19

Как бороться с паузами java приложения, не трогая GC

Java *
Сколько раз мне приходилось настраивать GC, чтобы вылечить приложение, у которого время от времени случается приступ, и оно перестает временно выполнять свои функции. Работа, скажу, не самая занимательная и требует хорошего знания матчасти. В данном топике я опишу какие еще есть способы решения данной проблемы.
Читать дальше →
Total votes 40: ↑30 and ↓10 +20
Views 3.5K
Comments 29

3 миллиарда записей в Java Map на 16 GB RAM

Java *
Sandbox
Одним дождливым вечером я размышлял о памяти менеджмент в Java и как эффективно использовать Java коллекции. Я сделал простой эксперимент, сколько записей я могу вставить map с 16 Гб оперативной памяти?
Читать дальше →
Total votes 53: ↑24 and ↓29 -5
Views 15K
Comments 16

Структуры данных, PHP. Часть вторая

PHP *
Translation
Tutorial
Продолжаю совмещать приятное с полезным и переводить. Сегодня речь зайдет о кучах (heaps) и графах. Как обычно, материал скорее подойдет новичкам — большая часть информации, если не вся, уже где-то так или иначе освещалась.

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

UPD: Добавил сравнение производительности
Читать дальше →
Total votes 37: ↑29 and ↓8 +21
Views 34K
Comments 18

J-сортировка

Programming *Java *Algorithms *

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

Так ещё метод и прост до безобразия
Total votes 57: ↑53 and ↓4 +49
Views 83K
Comments 17

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

C++ *Concurrent computing *Development for Windows *
Sandbox
image

Предисловие


Данная статья выросла из проблемы, которую мне относительно недавно пришлось решить: скорость кода, предназначенного для работы одновременно в нескольких потоках, резко упала после очередного расширения функционала, но только на Windows XP/2003. С помощью Process Explorer я выяснил, что в большинство моментов времени исполняется только 1 поток, остальные находятся в ожидании, причём TID активного потока постоянно меняется. На лицо явная конкуренция за ресурс, и этим ресурсом оказалась куча по умолчанию (default heap). Новый код активно использует динамическое выделение/высвобождение памяти (копирование строк, копирование/модификация STL контейнеров большого размера), что собственно и привело к возникновению данной проблемы.

Немного теории


Как известно, аллокатор по умолчанию (default allocator) для STL контейнеров и std::basic_string (std::allocator) выделяет память из кучи по умолчанию, а операции выделения/высвобождения памяти в ней являются блокирующими (косвенное подтверждение). Исходя из этого, при частых вызовах HeapAlloc/HeapFree мы рискуем намертво заблокировать кучу для других потоков. Собственно это и произошло в моём случае.

Читать дальше →
Total votes 22: ↑21 and ↓1 +20
Views 12K
Comments 33

Эксперименты с malloc

VK corporate blog C *Development for MacOS *
image

Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge*. Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc/<pid>/maps, в OS X vmmap <pid>. У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.

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

  • оптимально управляет уже выделенной памятью;
  • значительно уменьшает количество обращений к ядру (ведь mmap / sbrk — это syscall);
  • вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.

Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.
Читать дальше →
Total votes 59: ↑58 and ↓1 +57
Views 33K
Comments 11

Exploit Exercises: Введение в эксплуатацию бинарных уязвимостей на примере Protostar

Information Security *Reverse engineering *CTF *
Tutorial


Всем доброго времени суток. Продолжаем разбор заданий с сайта Exploit Exercises, и сегодня будут рассмотрены основные типы бинарных уязвимостей. Сами задания доступны по ссылке. На этот раз нам доступны 24 уровня, по следующим направлениям:

  • Network programming
  • Byte order
  • Handling sockets
  • Stack overflows
  • Format strings
  • Heap overflows
Читать дальше →
Total votes 20: ↑20 and ↓0 +20
Views 18K
Comments 0

Эксперименты с malloc и нейронными сетями

VK corporate blog Python *System Programming *Algorithms *Machine learning *


Больше года назад, когда я работал антиспамщиком в Mail.Ru Group, на меня накатило, и я написал про эксперименты с malloc. В то время я в свое удовольствие помогал проводить семинары по АКОСу на ФИВТе МФТИ, и шла тема про аллокацию памяти. Тема большая и очень интересная, при этом охватывает как низкий уровень ядра, так и вполне себе алгоритмоемкие структуры. Во всех учебниках написано, что одна из основных проблем динамического распределения памяти — это ее непредсказуемость. Как говорится, знал бы прикуп — жил бы в Сочи. Если бы оракул заранее рассказал весь план по которому будет выделяться и освобождаться память, то можно было составить оптимальную стратегию, минимизирующую фрагментацию кучи, пиковое потребление памяти и т.д. Отсюда пошла возня с ручными аллокаторами. В процессе раздумий я натолкнулся на отсутствие инструментов логирования malloc() и free(). Пришлось их написать! Как раз про это была статья (а ещe я изучал macOS). Были запланированы две части, однако жизнь круто повернулась и стало не до malloc(). Итак, пора восстановить справедливость и реализовать обещанное: ударить глубоким обучением по предсказанию работы с кучей.


Внутри:


  • Совершенствуем libtracemalloc, перехватчик malloc().
  • Строим LSTM на Keras — глубокую рекуррентную сеть.
  • Обучаем модель на примере работы реального приложения (vcmi/vcmi — а вы думали, причем здесь Heroes III?).
  • Удивляемся неожиданно хорошим результатам.
  • Фантазируем про практическое применение технологии.
  • Исходники.

Интересно? Добро пожаловать под кат.


Читать дальше →
Total votes 72: ↑72 and ↓0 +72
Views 25K
Comments 15

Особенности использования и тестирования кода С++ на микроконтроллерах

IOT IT-companies
Так сложилось, что основным языком для работы с микроконтроллерами является C. Многие крупные проекты написаны именно на нем. Но жизнь не стоит на месте. Современные средства разработки уже давно позволяют использовать C++ при разработке ПО для встраиваемых систем. Однако такой подход до сих пор встречается достаточно редко. Не так давно я попробовал использовать С++ при работе над очередным проектом. Об этом опыте я и расскажу в данной статье.

Читать дальше →
Total votes 18: ↑16 and ↓2 +14
Views 21K
Comments 55

Три вида утечек памяти

Издательский дом «Питер» corporate blog High performance *Python *C++ *Virtualization *
Translation
Здравствуйте, коллеги.

Наши долгие поиски неустаревающих бестселлеров по оптимизации кода пока дают лишь первые результаты, но мы готовы вас порадовать, что буквально только что закончен перевод легендарной книги Бена Уотсона "Writing High Performance .NET Code". В магазинах — ориентировочно в апреле, следите за рекламой.

А сегодня предлагаем вам почитать сугубо практическую статью о наиболее насущных видах утечек оперативной памяти, которую написал Нельсон Ильхейдж (Nelson Elhage) из компании Stripe.
Читать дальше →
Total votes 19: ↑17 and ↓2 +15
Views 11K
Comments 13

Моя ошибка на миллиард долларов

Project management *Product Management *
Translation
В первое время мне часто хотелось сдаться. Снова и снова возникало чувство, что мы всё делаем неправильно. Делать предположения о проблемах людей. Решать проблемы, которые мы придумали. Мы искали решения в темноте. У нас было ясное видение, но исполнение страдало.

Мы знали только то, что хотим заново изобрести рынок аналитики. Нашей первой попыткой стала аналитическая платформа для разработчиков приложений Facebook, потому что в то время у них не было эффективных аналитических систем, им приходилось разрабатывать собственные.

Продукт создавался для разработчиков приложений Facebook — и он им понравился! Только они не могли нам заплатить.

Читать дальше →
Total votes 18: ↑17 and ↓1 +16
Views 6.1K
Comments 1

Динамическая память в системах жёсткого реального времени

Open source *System Programming *Algorithms *C *Programming microcontrollers *
🔥 Technotext 2020

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



(КДПВ – см. аннотацию к диаграмме в конце)

Читать дальше →
Total votes 61: ↑60 and ↓1 +59
Views 14K
Comments 52

Go: Должен ли я использовать указатель вместо копии моей структуры?

Programming *Go *
Translation
image
Иллюстрация, созданная для «A Journey With Go», из оригинального гофера, созданного Рене Френч.

С точки зрения производительности систематическое использование указателей вместо копирования самой структуры для совместного использования структур многим Go разработчикам представляется наилучшим вариантом. Для того чтобы понять влияние использования указателя вместо копии структуры мы рассмотрим два варианта использования.
Читать дальше →
Total votes 32: ↑23 and ↓9 +14
Views 12K
Comments 27

Языковая механика стеков и указателей

Programming *Go *
Translation

Прелюдия


Это первая из четырех статей в серии, которая даст представление о механике и дизайне указателей, стеков, куч, escape analysis и семантики значения/указателя в Go. Этот пост посвящен стекам и указателям.

Оглавление цикла статей:

  1. Language Mechanics On Stacks And Pointers
  2. Language Mechanics On Escape Analysis (перевод)
  3. Language Mechanics On Memory Profiling (перевод)
  4. Design Philosophy On Data And Semantics

Вступление


Не буду лукавить — указатели трудны в понимании. При неправильном использовании указатели могут вызвать неприятные ошибки и даже проблемы с производительностью. Это особенно верно при написании конкурентных или многопоточных программ. Неудивительно, что многие языки пытаются скрыть указатели от программистов. Однако, если вы пишете на Go, вы не сможете избежать указателей. Без четкого понимания указателей вам будет сложно писать чистый, простой и эффективный код.
Читать дальше →
Total votes 8: ↑7 and ↓1 +6
Views 4.7K
Comments 7

Языковая механика escape analysis

Programming *Go *
Translation

Прелюдия


Это вторая из четырех статей в серии, которая даст представление о механике и дизайне указателей, стеков, куч, escape analysis и семантики значения/указателя в Go. Этот пост посвящен кучам и escape analysis.

Оглавление цикла статей:

  1. Language Mechanics On Stacks And Pointers (перевод)
  2. Language Mechanics On Escape Analysis
  3. Language Mechanics On Memory Profiling (перевод)
  4. Design Philosophy On Data And Semantics

Вступление


В первом посте из этой серии я рассказал основы механики указателя на примере, в котором значение распределяется по стеку между горутинами. Я не показывал вам, что происходит, когда вы разделяете значение в стеке. Чтобы понять это, вам нужно узнать о другой области памяти, где могут находиться значения: о «куче». С этим знанием вы можете начать изучать «escape analysis».
Читать дальше →
Total votes 7: ↑6 and ↓1 +5
Views 4.3K
Comments 1

Языковая механика профилирования памяти

Programming *Go *
Translation

Прелюдия


Это третья из четырех статей в серии, которая даст представление о механике и дизайне указателей, стеков, куч, escape analysis и семантики значения/указателя в Go. Этот пост посвящен профилированию памяти.

Оглавление цикла статей:

  1. Language Mechanics On Stacks And Pointers (перевод)
  2. Language Mechanics On Escape Analysis (перевод)
  3. Language Mechanics On Memory Profiling
  4. Design Philosophy On Data And Semantics

Посмотрите это видео, чтобы увидеть демонстрацию этого кода:
DGopherCon Singapore (2017) — Escape Analysis

Вступление


В предыдущем посте я обучил основам escape analysis, используя пример, который разделяет значение в стеке горутины. Я не показал вам других сценариев, которые могут привести к переносу значений в кучу. Чтобы помочь вам с этим я собираюсь отладить программу, которая делает аллокации неожиданным образом.
Читать дальше →
Total votes 7: ↑6 and ↓1 +5
Views 2K
Comments 0
1