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

Мне по работе часто приходится сталкиваться с высоконагруженными многопоточными или многопроцессными сервисами (application-, web-, index-server).
Достаточно интересная, но иногда неблагодарная работа — оптимизировать все это хозяйство.
Растущие потребности клиентов часто упираются в невозможность просто заменить железную составляющую системы на более современную, т.к. производительность компьютеров, скорость чтения-записи жестких дисков и сети растут много медленнее запросов клиентов.
Редко помогает увеличение количества нодов кластера (система как правило распределенная).
Чаще приходится запустив профайлер, искать узкие места, лезть в source code и править ляпы, которые оставили коллеги, а иногда и сам, чего греха таить, много лет назад.
Некоторые из проблем, связаных с синхронизацией, я попытаюсь изложить здесь. Это не будет вводный курс по многопоточному программированию — предпологается, что читатель знаком с понятием thread и context switch, и знает для чего нужны mutex, semaphore и т.д.

David Drysdale, Beginner's guide to linkers (http://www.lurklurk.org/linkers/linkers.html).

Цель данной статьи — помочь C и C++ программистам понять сущность того, чем занимается компоновщик. За последние несколько лет я объяснил это большому количеству коллег и наконец решил, что настало время перенести этот материал на бумагу, чтоб он стал более доступным (и чтоб мне не пришлось объяснять его снова). [Обновление в марте 2009: добавлена дополнительная информация об особенностях компоновки в Windows, а также более подробно расписано правило одного определения (one-definition rule).

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

g++ -o test1 test1a.o test1b.o
test1a.o(.text+0x18): In function `main':
: undefined reference to `findmax(int, int)'
collect2: ld returned 1 exit status

Если Ваша реакция — 'наверняка забыл extern «C»', то Вы скорее всего знаете всё, что приведено в этой статье.

Не секрет, что не одно поколение программистов зачитало до дыр книгу «Этюды для программистов» Чарльза Уэзерелла, оригинал которой на английском вышел аж в 1978.



Книга содержит 27 “этюдов”. Каждый этюд – это законченная содержательная задача для обучающихся программированию. Удивительно, книге более 30 лет, но любой из этюдов может быть до сих пор использован по назначению. Сам, будучи фанатом книги, до сих пор храню родной бумажный вариант русского издания, а относительно недавно таки приобрел оригинал на английском.

Увы, о самом авторе было очень мало информации, и более того — не было продолжения или новых книг, чтобы крайне странно после столь хорошей первой книги.

Волею судеб, недавно у меня появилась возможность связаться с Чарльзом и взять у него интервью.

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

Считается, что сборщик мусора – черный ящик, работу которого нельзя предугадать.

А еще говорят, что GC в .NET практически не настраиваемый. А еще, что нельзя посмотреть исходники как классов .NET Framework, так и CLR, GC и т.п.

А я скажу как бы ни так!

В данной статье мы рассмотрим:

• структура организации размещения объектов в памяти
• CLR 4.5 Background Server GC
• правильная настройка сборщика мусора
• эффективный апгрейд приложений до .NET 4.0+
• правильное ручное управление памятью

Здравствуйте, Хабраюзеры.
Недавно я прочитал здесь статью об анонимных функциях в С++, и тут же у меня в голове возникла мысль: нужно срочно написать класс для работы с функциями, которые нам знакомы из математики. А именно, принимающими вещественный аргумент и возвращающими вещественное же значение. Нужно дать возможность обращаться с такими объектами максимально просто, не задумываясь о реализации.
И вот, как я это реализовал.

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

Хотя постойте, знаете ли вы какова сложность функции size ()?
«Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»

size_type  size() const                             
{
       return _size;
}

Тривиально, эффективно и безопасно, не так ли?
Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.

Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.

Существует определенный набор возможностей в любом языке программирования для понимания которых нужно просто знать, как они реализованы. Вот, например, замыкания; это не сверх сложная концепция, но знание того, как этот зверь устроен позволяет делать определенные выводы относительно поведения замыканий с переменными цикла. Тоже самое касается вызова виртуальных методов в конструкторе базового класса: здесь нет одного правильного решения и нужно просто знать, что именно решили разработчики языка и будет ли вызываться метод наследника (как в Java или C#), или же «полиморфное» поведение в конструкторе не работает и будет вызываться метод базового класса (как в С++).

Еще одним типом проблемы у которой нет идеального решения, является совмещение перегрузки методов (overloading) и переопределения (overriding) метода. Давайте рассмотрим следующий пример на языке C#. Предположим, у нас есть пара классов, Base и Derived, с виртуальным методом Foo(int) и невиртуальным методом Foo(object) в классе Derived:

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

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

Когда участвуешь в разработке достаточно сложных проектов, то написать неправильно работающий код проще простого. Вся загвоздка заключается в том, что ошибку начинаешь искать в самых темных закоулках проекта, в самых сложных его частях. При этом в голову даже и мысли не приходит, что не работать может самый простой код, основа всего проекта: framework.
В данном посте я опишу две проблемы, с которыми я столкнулся на практике: невозможность создать еще один поток и переименовать файл. Используемый язык программирования: C/C++.

Язык C++ для всех пользовательских классов и структур генерирует по умолчанию копирующий конструктор и копирующий оператор присваивания. Тем самым для важного ряда случаев программист освобождается от написания указанных функций вручную. Например, операторы по умолчанию хорошо работают для структур, которые содержат данные. При этом данные могут храниться как в простых типах, так и в сложных контейнерах, таких как std::vector или std::string.

В свете этого удобно было бы иметь и операторы сравнения структур == и != по умолчанию, однако компилятор C++, в соответствии со стандартом, не генерирует их.

«Система должна быть спроектирована так,
чтобы оставаться как можно проще
после серии внесенных в нее изменений»
Бьярне Строуструп – программист, автор языка C++

Преамбула

В данной статье мне бы хотелось бы рассказать о довольно популярной, но так редко освещаемой на Хабре библиотеке Portable Components (сокр. POCO). Она будет полезна как разработчикам бизнес-логики программного продукта, так и в решении большинства прикладных задач. При всем изобилии кроссплатформенных библиотек для C++ всё больше людей сталкиваются с POCO лицом к лицу и не знают с чего начать. В данной статье я постараюсь описать технологии, заложенные в библиотеке и дать простейшие примеры решения некоторых задач. Также хотелось бы отметить, что за плечами библиотеки множество успешных как Open Source, так и коммерческих проектов.

Паттерн Singleton появился, пожалуй, как только появились статичные объекты. В Smalltalk-80 так был сделан ChangeSet, а чуть в самых разных библиотеках стали появляться сессии, статусы и тому подобные объекты, которых объединяло одно — они должны были быть одни-единственные на всю программу.

В 1994 году вышла известная книга «Паттерны проектирования», представив публике, среди 22-х прочих, и нашего героя, которого теперь назвали Singleton. Была там и его реализация на C++, вот такая:

Доброго времени суток!

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

Самое главное, что необходимо помнить — перегрузка операторов, это всего лишь более удобный способ вызова функций, поэтому не стоит увлекаться перегрузкой операторов. Использовать её следует только тогда, когда это упростит написание кода. Но, не настолько, чтобы это затрудняло чтение. Ведь, как известно, код читается намного чаще, чем пишется. И не забывайте, что вам никогда не дадут перегрузить операторы в тандеме со встроенными типами, возможность перегрузки есть только для пользовательских типов/классов.

Автор: Alexander Sandler, оригинал статьи (23 декабря 2008)

Введение

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

Автор: Alexander Sandler, оригинал статьи (27 мая 2009)

Введение

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

Доброго времени суток!
Некоторым программистам иногда приходит в голову мысль «а не изучить ли мне ассемблер?». Ведь на нем пишут самые (с некоторыми оговорками) маленькие и быстрые программы, да и охота ощутить вкус низкоуровневого программирования берет свое. Ну и для общего развития не повредит.
Мысль эта не обошла стороной и меня. Вдохновившись историей одного байта, я ринулся в бой…

… но оказалось, что найти материал по интересующей теме не так просто, как хотелось бы. Посему решено было создать на хабре пополняющийся пост-индекс статей/книг/мануалов/etc. об этом, несомненно, великом языке.
Под катом находится, собственно, список с краткими комментариями, разбитый по категориям.

UPD
В список начали добавляться ресурсы по программингу микроконтроллеров.

Архипенков Сергей — эксперт в управлении разработкой ПО, более 30 лет в разработке ПО, PMP® PMI, вице-президент Гильдии менеджеров программных проектов. Активный «продвигатор» и «задвигатор» теории и практики управления проектами и людьми в проектах по разработке ПО. Активный заседатель программных комитетов. Из последнего — председатель программного комитета конференции «Software Project Managment Conference» (ноябрь, Санкт-Петербург).

Ниже опубликован доклад Сергея с конференции CodeFest, на тему «Теория и практика адаптивного управления проектом».

Эта тема не относится к IT напрямую, но все знают, что без нее никуда. К сожалению, далеко не у всех есть возможность изучать английский с преподавателями. Ну что ж, попробуем заняться этим дома и с максимальной отдачей!