yigal_s | Entries tagged with programming

Profile

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

http://groups.google.com/group/lock-free/browse_thread/thread/d7ac22f807d1d439

Возможно и похоже (я не проверял, у меня сейчас на виндах нет ни дебаггера ни даже С++, а дискуссия по ссылке чуток неадеквата), что сейчас под виндоуз невозможно написать 100% надёжный lock-free код, возвращающий память системе с помощью вызова free и подобного, а не возвращающий выделенную память в пул, либо использующий сборщик мусора.

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

Проблема, однако, в том, что адресуясь по устаревшим указателям наугад можно нечаянно задеть guard-page другого треда, а это, как это не смешно, приводит через непродолжительное время к терминации процесса.

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

Вообще, чего б этому самому ядру не заботиться о том, чтобы не сносить аттрибут guard-pages если они не относятся к стеку текущего треда? Ведь уже так или иначе исключение по доступу к guard page стека делается в kernel-mode, так отчего бы и нет? Впрочем, тогда либо придется вводить дополнительный аттрибут памяти "stack guard page", либо тупо проверять, а не относится ли данный guard-page на который нечаянно наступили, к какому-нибудь еще стеку, что действительно довольно тупо. Опять же, если продвинутый пользователь желает использовать guard-pages сам для своих собственных структур данных (а не для стека треда), то чужой тред снова имеет чудесную возможность долбануть по этому guard-page, получить исключение и поднять лапки кверху, поскольку что делать с этим исключением он не знает.

В общем, весь концепт guard-page задизайнен, похож, немного криво.
----------------------------------
С другой стороны, как отмечают тут (ссылка аж с 2003-го года!) память может быть замаплена и на порты ввода-вывода устройств, и тут уже остается не жаловаться на кривой дизайн или имлементацию guard-page, а просто, видимо, обозначить, что lock-free синхронизацию принципиально нельзя делать без поддержки сборщика мусора (которому самому желательно быть lock-free :-))) или рецайлинга объектов (даже не памяти, а именно объектов, чтобы будущие адресации нечаянно не попали на переалллоцированный объект другого формата).

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

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

Скажем, если я профайлю какую-то функцию, которая занимает 3 секунды абсолютного времени и 1 секунду процессоного, то было б неплохо знать, на что ушли оставшиеся две секунды - на ожидание ресурсов, или на ожидание свободного ядра. Как бы, время на ожидание свободного ядра можно смело выкидывать из статистики по профилированию аппликации, оно не интересно.

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

Вроде бы ни юникс, ни винды такую статистику не дают.

----------

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

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

В рамках стандарта. :-)

Чем хороший мультитредный программист отличается от плохого?

Плохой, как правило, знает, как написать мультитредный код, а хороший - как правило, не знает.

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

Если плохой мультитредный программист должен починить баг в коде, написанном другими плохими программистами - он как правило вставляет еще одну блокировку. Либо же убирает её. Хорошему в этом случае обычно приходится переписывать пол-проекта, меняя интерфейсы и архитектуру. В том редком случае, когда он всё же находит способ убедить себя, что он может починить этот баг.

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

Плохой программист умеет пользоваться мютексом, программист получше семафором, самый лучший из плохих - кондваром. Хороший программист знает, что он не умеет пользоваться ничем.

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

Некоторые хорошие мультитредные программисты умеют притворяться плохими и эмулировать их способности. При необходимости.

А почему б не считать класс параметризованный приватным классом - опять же приватным...
а не ломать компиляцию почем зря.

Имплементировал эмуляцию отсутствующих пока в С++ "template typedefs". Ничего оригинального, известный workaround. Вводим nested typedef, и рассматриваем внешний темплейтный класс как "темплейтный typedef"

Плюс, что небезынтересно, сделал универсальный адаптер, который позволяет работать с обычными темплейтами и с темплейтными typedefs единообразно. Это, как бы, уже возможность всерьёз использовать такие вещи в production code. Если не страшно. :-)))
( Детали под катом )

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

template <class T>
class Type1
{
public:
};

template <class T>
class Type2
{
public:
    enum { HREN };

};

Товарищ Андрей Александреску, известный мне не только как гениальный С++ программист и извращенец в хорошем смысле этого слова, но и как автор довольно позорных статей и утверждений в области мультитреда (видно, сказалось головокружение от успехов), оказывается, еще в старом 2004-м году рекламировал на страницах DDJ идеи lock-free программирования, вполне подробно и внятно описывая его преимущества:

http://www.drdobbs.com/cpp/184401865

и даже написал продожение к этой статье "в соавторстве" с Магедом Майклом, звездой мирового уровня в этом самом lock-free.

http://www.drdobbs.com/184401890 (еще не прочитал)

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

внезапно оказалось, что пишу я код под процессор, у которого кроме операции InterlockedExchange ничего интерлоканного и нет. Это, значица, 2-е десятилетие 21го века на дворе, а у нас лошади не сёдланы даже.

Стало мне от этого немного грустно, и вздумалось реализовать все остальные интерлок-операции через эту единственную.

Начал я с InterlockedAdd. Вот такая штука получилась (пишу коряво, лишь чтобы идею передать). Не знаю, заработает ли, но по идее, должно ;-)

LONG InterlockedExchangeAdd(int *pval, int delta)
{
   int cur = *pval;
never_again:
   int result = cur + delta;
   int newVal = InterlockedExchange(pval, result); // aka asm xchg
   if( newVal != cur )
   {
       delta = newVal - cur;
       cur = newVal;
       goto never_again;
   }
   return cur; 
}

Теперь осталось сымплементировать InterlockedComparedExchange, и можно садиться писать диссертацию.

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

Ну, скажем, в Intel x86 можно считать, что на каждой команде записи в память стоит release-барьер, а на каждой команде чтения из памяти стоит acquire-барьер, а на каждой lock-инструкции стоит двусторонний барьер, но вот что означает слово "total" в предложении "locked instructions have a total order", и почему об этом вообще надо отдельно говорить, до меня как-то не доходило.

Вот, скажем, и по этой ссылке http://www.bluebytesoftware.com/blog/2008/07/17/LoadsCannotPassOtherLoadsIsAMyth.aspx далеко не последний человек в Микрософте и автор толстенной книжки по мультитреду выглядит смущенным фактом того, что не существует самого по себе "общего порядка", "total order" исполнения операций процессорами. Тот факт, что два процессора могут быть несогласны относительно того, кто из них раньше, а кто позже выполнил свою операцию записи в память он трактует как то, что операции чтения из памяти могут переупорядочиваться (мол, вопреки обещаниям компинии Intel и вопреки спекам процессора). Меж тем, никакого абсолютного "раньше и позже" тут нет, поскольку речь идет о чтении данных, записанных двумя разными процессорами. И в этом всё дело.

На ньюсгруппе comp.programming.threads некий постоянный и вполне квалифицированный участник (гуру?) David Schwartz из года в год упорно твердит одно и то же: lock free "синхронизация" - неэффективна. Это при том, что последние годы только о ней, кажется, повсюду и говорят когда заходит речь о мультитрединге.

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

А именно, как я понял, David утверждает( Read more... )

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

Это куда как проще оказывается. :-)))

У меня, скажем, как-то валялась статья, в которой я года 3 не мог разобраться. Ну не простой там был код, не простой. Пока, наконец, за одно утро, сидя в очереди к врачу, я не понял, что код - просто туфта. Т.е. показатель эффективности (отношение времени потраченного на разбор кода ко времени потраченному на его разгром) - несколько сотен. И если б это было единожды...

Интересно было б придумать два таких интерфейса A и B, состоящие из поднабора методов A1, A2 и B1 и B2, таких что по подинтерфейсам A1 был бы подтипом B1, а A2 был бы супертипом B2.

Вот, скажем, с точки зрения константных методов, квадрат есть подтип прямоугольника, ( Read more... )

А не забавно ли, мягко говоря, что начинающий программист на Win32 мало того, что не способен написать thread-safe синглетон, но и, в сущности, вряд ли сможет понять мало-мальски эффективное решение, не прослушав перед этим получасовую, как минимум, лекцию?

http://community.livejournal.com/ru_cpp/366267.html

Что важно, ситуация такая имеется только под Win32, поскольку на юниксовых pthreads есть статичиски-инцициализируемые критические секции, не говоря уже о давно существующем pthread_once, и программист может просто тупо пользоваться этими вещами и не забивать себе голову всякой платформенной эзотерикой.

Кстати 1: на Висте вещи вроде pthread_once тоже есть.
Кстати 2: fast_pthread_once

Оказывается, год назад Intel опубликовало спек на модель упорядочивания доступов к памяти своих процессоров IA-32 и x64 . Подробно описала каким образом доступы к памяти могут переупорядочиваться и как их можно насильно упорядочить.

И вот тут

http://www.justsoftwaresolutions.co.uk/threading/intel-and-amd-memory-ordering-defined.html

даже написали, что теперь из этого документа достоверно известно, что

( Read more... )

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

http://community.livejournal.com/ru_cpp/347512.html

В кои-то веки я дорвался до GUI.

Удачным решением порадовал Микрософт программистов новой 64-битной платформы.
Теперь, если окно обрабатывает оконное сообщение, пришедшее из другой аппликации или даже из другого треда той же аппликации, и при этой обработке случается исключение (ну, например, такая мелочь как Access Violation), то аппликация пользователя вовсе не крешится, а продолжает себе работать как ни в чем не бывало.

Подробнее - исключение долетает до участка кода, пробрасывающего в окно "внешние" сообщения, и там окончательно поглощается, вообще не долетая до основного кода аппликации. Излишне говороить, что при поглощении UnhandledExceptionFilter не вызывается.

Кажется, подобной надежностью (толерантностью к исключениям) обладали раньше и COM сервера, теперь же и обычные пользовательские апплкации 64-х битной платформы. К сожалению, если оконное сообщение было послано тем же самым тредом, как это обычно бывает в GUI-программировании, то аппликация всё-таки может закрешиться, так как исключение уже никто по дороге не словит. Это может создать ложное впечатление о неработоспособности аппликации у QA и даже конечного пользователя. Надеюсь, в будущих версиях этот недочет будет исправлен.

Пора бы как-то разобраться с ООП и закрыть эту тему для себя. По возможности, окончательно. Предварительные выводы, скорее уж проектируемые направления работы:

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

2. Наследование (классов от других классов) есть некоторый (со своими возможными граблями) паттерн повторного использования кода, поддерживаемый языком. Вообще, ввод понятия класса есть опять же некий паттерн реализации минимальных функциональных элементов в ООП. Чтобы разобраться в ООП, идею наследования и классов желательно подвинуть в сторону.

3. ООП не универсально. Не всё ложится в его схему, и не должно ложиться. Даже моделирование объектов внешнего мира может не уложиться в конкретную ООП-схему. Может ли уложиться хоть в какую-то -- вопрос открытый. Им стоит заняться.

4. Правильное построение механизма наследования и типизации есть крайне нетривиальная задача. Только после проработки первых трёх пунктов имеет смысл ей как-то заняться.

1. поразительно, как много людей, особо заточивших свой моск под MS Windows(tm) считают, что достаточно критических секций (на крайняк, read-write lock-ов) для того, чтобы писать практически что угодно в мультитреде. В чем они правы, так это в том, что на критических секциях действительно можно написать немало, и порой, можно написать относитльно нетривиальные вещи. И всё же... если такого человека спросить, хватит ли ему критических секций, чтобы написать всё, что угодно, то он, конечно же, немедленно вспомнит об...

2. Об Event-ах. Интересно было бы узнать детальную историю, кто и как додумался включить автоматические и мануальные Eventы в Windows. Кто. И как. И кто. Кто этот враг рода человеческого, и о чем думали в это время его коллеги? Наверное, Events появились в PL/1. Впрочем, были ли там мануальные Events? Были ли Events в DEC-овских операционных системах, откуда (из DEC) пришли разработчики NT Kernel? Придумал ли Events человек с хорошим бекраундом в электронике? (ведь ожидание event так напоминает ожидание фронта или уровня сигнала!)

3. Уж сколько лет существует .NET, Java, не говоря уже о POSIX. Но стоит произнести слово "conditional variable", в ответ, как правило, видишь лишь недоуменный взгляд. Потому что, как уже было отмечено, критических секций достаточно. Практически на всё. И это почти правда.

4. Попробуйте реализовать condvar под Windows. Ну попробуйте! Создатели ACE попробовали, даже статью написали об этом. О шести неправильных вариантах реализации и о седьмом. Потом оказалось, тоже неправильном. Всё-таки, другие люди потом придумали правильную реализацию. Они так говорят. Я им не очень верю, но всё равно преклоняюсь, ибо в том, что они написали, я вообще ничего пока понять не могу.

5. Впрочем, всё это суета. Ибо всё это уже давно очень слегка подустарело. О чем, опять же, промышленному кодеру знать и не обязательно. Промышленному кодеру освоить хотя бы The Little Book of Semaphores, потом отложить её в сторону и... снова заняться расстановкой критических секций в коде. Чтоб не сбоил, ага.

the term spaghetti stack is closely associated with implementations of programming languages that support continuations. Spaghetti stacks are used to implement the actual run-time stack containing variable bindings and other environmental features. When continuations must be supported, a function's local variables cannot be destroyed when that function returns: a saved continuation may later re-enter into that function, and will expect not only the variables there to be intact, but it will also expect the entire stack to be there, so it can return again! To resolve this problem, stack frames can be dynamically allocated in a spaghetti stack structure, and simply left behind to be garbage collected when no continuations refer to them any longer. This type of structure also solves both the upward and downward funarg problems, so first-class lexical closures are readily implemented in that substrate also.

via wikipedia

http://mustread.ru/isbn/013507245x.html

"Фишка такая. Программы следует писать, не используя рекурсии, циклов и их заменителей. Вообще. Вместо этого следует использовать хрень под названием "катаморфизм"."

http://vewacs.livejournal.com/

кстати, обнаружилась:

The theory and practice of concurrency, Prentice Hall, 1998 [pdf]

вряд ли я это одолею, но вдруг?

+страница автора
http://web.comlab.ox.ac.uk/oucl/work/bill.roscoe/pubs.html

ой, какой раритет появился:
Пильщиков. "Язык Плэнер" (советская серия "библиотечка программиста")
[link]
да еще скан экземпляра за подписью автора.

Сейчас медитирую перед четырьмя небезынтересными и там-сям рекомендованными книшками:

Хендерсон П. - Функциональное программирование, применение и реализация -- пока напечатал и прочитал несколько десятков страниц, вводит в тему на неплохой очень скорости, изложение строится вокруг Лиспа. Интересно. Но пока мало прочитал.

А.Филд, П.Харрисон - Функциональное программирование -- вводят свой, кажется, язык Hope, чисто функциональный с возможностью ленивых вычислений и строгой типизацией. В общем, тоже про реализацию в основном. Прочитал где-то четверть, введение в тематику. Слегка нудновато, порой не очень ясно, но в целом смысл очень наличествует.

John Harrison - Introduction to Functional Programming -- пока не открывал. Обсуждаемый язык - ML

Хювёнен, Сеппянен - Мир Лиспа. -- пол-первого тома мне показались фатально скучными. Потуги автора на оригинальность (какие-то иконки на полях книги) не вдохновили. Пожалуй, если бы не имел отрывочной информации по Common Lisp, то и не осилил бы. Второй том, впрочем, обещает быть очень насыщенным чем-то вполне нетривиальным. Кажется. Будет время - буду вычитывать дальше. Со стоном.

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

Вообще, забавно, что в тематику функционального программирования я мог бы влезть очень давно. Но... что из чтения книги по Плэнеру, что по Лиспу (та же "библиотечка программиста"), еще в студенческие времена, идея чистого функционального программирования у меня не выкристализовалась. Никак. Ну скобки и скобки (интересно, конечно), ну присваивание, ну бектреккинг... То ли главного не уловил, то ли в Пленнере и Лиспе это и не главное. :-) Как не странно, идею точечной пары, прочих конструкторов типа и программирования ~~с использованием чистых функций~~ без изменяемых переменных я усвоил из... Пролога. В котором это, впрочем, опять же, видимо, не главное.

давным давно, когда boost еще не было, а меня еще не уволили с одной весьма хайтековской фирмы за использования макросов, темплейтов, исключений и мультитрединга (в совокупности) на любимом С++, я начал пробовать (не в реальных проектах, упаси бох) разные странные вещи. Вроде темплейтизированного определения константности, темплейтизированных указателей (не smart poiners с накрученной run-time функциональностью, а просто обычных указателей, но завернутых в темлпейты) и чего-то там еще.

Вот скажем, вам не приходило в голову, что ( Read more... )

На знаменитом ныне sql.ru (где ксеноцефал) я недавно обнаружил упоминание работ Luca Cardelli из Microsoft Research.

На мой вкус, колоссальный чувак. ( Read more... )

немного поработал над пониманием ~~глубокой философии~~ уродств прекрасного С++

здесь

Вкратце, каждый уважающий себя объект должен имплементировать метод

C& C::takeme()

{

return *this;

}

Ой.

----
Upd: впрочем, можно и так:

C::operator C&( )

{

return *this;

}

Не сверялся со стандартом, но, похоже, это преобразование вызывается implicitly. Где надо.

~~Жить стало лучше, жить стало веселее.~~

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

( скучно о clearcase ucm (программизм-администризм) )

Был на курсе по мультитреду. Лектор оказался не вполне владеющим этим непростым материалом, да и вообще, по прочим сопряженным темам я узнал на лекциях много того, чего нет на самом деле. Некоторые ошибки имелись даже в письменных материалах к курсу. Ну, всё же, полезно потрепаться по теме, даже так. Активизирует. Даже очень (там ведь не совсем полная лажа была). Особо полезно когда платишь за курсы не ты, а фирма (хотя, в год меня по дефолту могут послать лишь на один курс, так что я не вполне эффективно пожег и некий личный ресурс). В общем, впечатления смешанные.

Задумался, стоило ли его, этого лектора, поправлять. Даже постфактум. Я и сейчас могу прислать ему список ошибок, отсутствующих существенных тем, итд итп. Но с другой стороны, зачем? Как бы не нанимался я ему помогать. Сделал неудачный курс? Вышел с ним на аудиторию? Так зачем МНЕ подчищать за ним, зарабатывающим, поди, раза в четыре больше, чем я, признанным мастером своего дела) его ошибки? Прими он (а можно и просто отмахнуться ведь, мол, пипл же хавает) все замечания во внимание, у него получится более добротный курс, но почему я должен делать добротный курс для него? Это, пожалуй, и просто смешно выйдет, если я, после того как меня вот слегка "развели", побегу помогать ИМ более качественно делать свой бизнес.

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

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

Всё равно как-то непонятно, как надо было в такой ситуации правильно поступить.

Где ООП явно не в тему - это ГУИ (пример правильного построения гуя - Fudgets).

[link]

Я так-сяк повертел это заявление (и прочие, прочитанные на sql.ru), вспомнил некоторые почему-то не получившиеся для написания задачи из своей практики, равно как и некоторые "гениальные ООП решения", и сформулировал супер-радикальный тезис:

Объектно ориентированное программирование менее всего подходит для отображения объектов реального мира (включая сюда и объекты - элементы GUI) в объекты (в терминологии OOP/D) программы.

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

Почитать, что ли Симулу какую... Для избавления от ереси неверия в то, во что верил последние 14 лет.

Видимо, написание самодокументируемого кода в принципе невозможно (а казалось ведь, что да).

1. Мало мальски нетривиальный алгоритм или математическую формулу возможно внятно запрограммировать, но никак невозможно разобрать среднему человеку. К формуле должен быть приложен её вывод (то есть, отсылка к тексту учебника), то же самое (отсылка к изложению идей алгоритма, обоснованию его правильности) и во втором случае.

2. Некоторые вещи пишутся для того, чтобы другие вещи (в другом куске кода) не падали или просто могли работать. Не в смысле написания каких-то дурацких заплаток. Вот например, "сейчас мы посчитаем вот это, потому, что это надо нам в другом месте, а там мы это посчитать уже не сможем". А тут мы возьмём критическую секцию потому, что если мы её не возьмём, то в другом месте обломаемся, хотя и факт того, что такая ситуация возможна сразу не очевиден. Без комментариев тут не обойтись.

3. Мало того, некоторые вещи можно, на первый взгляд, сделать разными способами, но выбираешь именно "вот этот способ", потому, что более очевидный приведёт к каким-то неочевидным сразу проблемам. И причину этого выбора придется комментировать, увы.

Смешно, что ранее этого четко не сознавал.

Я даже не знаю, как это отрекламировать.

Короче, если Вы не гениальный программист, возможно, Вам стоит это почитать

избиение младенцев

на 6-й странице из 66 я понял, что мертв профессионально. Собственно, это и раньше подозревалось, но не с такой ощутимой ясностью.

Продолжаю читать дальше. Весело. Конспектируя ссылочки.

via potan

xref

upd: прочитал всё полностью. жутко доволен

http://yosefk.com/c++fqa/

Эт сильно. Очень сильно. Чую, я буду это читать и перечитывать.

via link

Обработка исключений под Windows - это что-то особенное.

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

В XP тут вообще конь не валялся - стоит выгрузить код обработчка, так в ответ на исключение по вызову оного, вся карусель по исполнению обработчиков (уже нового) исключения заверчивается заново. И снова. И снова. Результат - переполнение стека.

В Win 2003 тут понаворотили стра-ашных "защит" - перед вызовом обработчика, проверяют, присутствует ли его код. Или что-то вроде того, я не вдавался. Кажется, правда, что и на XP проверяют, но эта проверка почему-то ничего не ловит. Опять же не вдавался. Короче говоря, в 2003 переполнения стека в этом сценарии не будет. Не будет. В этом сценарии. Зато они умеют, прямо там, выяснив, что обработчик исключения уже выгружен, немедленно корректно закрешить аппликацию. Вызвав (из под ntdll.dll) UnhandledExceptionFilter и всё на него навешенное.

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

Вот интересно, как можно абсолютно надежно вызвать следующую функцию Win32 API

SetUnhandledExceptionFilter()

чтобы вновь установленный фильтр мог вызвать старый?

Я бы, пожалуй, вызвал бы её из-под критической секции, а второй вход в ту же критическую секцию поставил бы вокруг считывания значения старого фильтра из-под нового. Дабы избегнуть ситуации, когда SetUnhandledExceptionFilter уже поставила новый фильтр, а старый фильтр (коий SetUnhandledExceptionFilter возвращает) еще не успели сохранить, и в этот самый момент из другого треда прилетает этот самый... unhandled exception и попадает в новый фильтр, у которого еще нет адреса старого.

Функция IsBadReadPtr и прочие из той же группы очень давно мне не нравились. Ну хотя бы тем, что в данный момент такая функция может выдать тебе, что по данному адресу можно что-то читать, а уже через долю секунды другой тред как-нибудь перераспредилит память, и читать уже не получится. То есть, думал я, не лучше ли сразу читать проблемную память из под try-except блока, не заморачиваясь предварительными проверками?

Реальность, однако, оказалась куда как хуже. Даже в чем-то безнадежной она оказалась.

Выяснилось, что:

если доступ к памяти "наугад", будь он сделан через IsBadReadPtr или же простое чтение памяти из-под try-except блока, нечаянно попадет на guard-страницу стека чужого треда,

то guard-аттрибут этой страницы будет снесён,

что впоследствии, когда стек второго треда подрастет за пределы той бывшей guard-страницы, приведет к "исчерпанию" стека этого треда и катастрофическому и молчаливому завершению всей аппликации.

Конечно, при касании guard-страницы, кидается STATUS_GUARD_PAGE_VIOLATION исключение, и можно было бы попытаться восстановить аттрибут guard-страницы. Можно было бы, если бы не очевидный race-condition: пока мы будем восстанавливаеть аттрибут, второй тред уже может навернуться. Функция же IsBadReadPtr попросту ловит все исключения, и обрабатывает их единообразно, и не пытаясь восстанавливать какие-то там аттрибуты.

И если бы только это...

Выяснилось, что безотносительно вышеупомянутых бед, функция IsBadWritePtr еще и способна повреждать данные в мультитредной аппликации! А именно, чтобы проверить, можно ли записать данные, она их сначала читает, а потом уже пишет прочитанное значение по тому же самому адресу. Если между чтением и записью какой-то другой тред изменит значение данных, то это измененное значение будет немедленно затерто старым.

Всё это, кстати, уже документировано на сайте msdn.

бляцкий ClearCase
чертов UCM

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

2. 1991 год. Во втором издании книги "Язык программирование С++" Страуструпа, exceptions было посвящено всего 30 страниц. Всё выглядит просто и красиво.

3. Конец 1994 года. Я тогда прекрасно разбирался в exceptions. В тех самых тридцати страницах. В журнале "С++ Report" появляется статья "Exception handling: a false sence of security", автор которой признается, что, видимо, не способен написать exception-safe стек (!) Вслед за ним свою неспособность сделать это, видимо, должен признать и средний, а то и продвинутый программист С++ того времени.

( еще шесть пунктов )

Дан массив из N элементнов. Ну, к примеру, integers
Делается копия этого массива, элементы в ней случайно перемешиваются, а 4 элемента просто выкидываются.
Теперь у нас имеется два массива - из N и N-4 элементов.
-----
Требуется - быстро найти значения удаленных четырёх элементов.

Upd: дополнительное условие - не аллоцировать дополнительных массивов.

1. Semaphores
2. Monitors (conditional variables).
3. Messages, рандеву, remote calls, actors (пока не разобрался, одно ли это и то же концептуально, или есть разница. Вообще, в принципе, больше "слышал звон", чем "в теме". Потихоньку разберусь)
4. transactional memory - несколько дней назад где-то ссылку на это дело подобрал.

Интересно, есть еще что-то неупомянутое?

-----
Upd: собственно, в списке представлена некоторая линия эволюции (хотя линейной эволюции в реальности, видимо, не было в точности) способов "синхронизации", вернее, написания мультитредного кода.

The most important problem with volatile correctness is that it relies on POSIX-like mutexes, and there are multiprocessor systems on which mutexes are not enough — you have to use memory barriers.

(с) Andrei Alexandrescu
http://www.ddj.com/dept/cpp/184403774

Интересно. Поиск на "on which mutexes are not enough" ничего не дал. Неужели никто не заметил?

ПС: редактора, конечно же, на мыло

> Проблема с С++ - это сложность в понимании/написании/употреблении мультитрединговой модели с точки зрения организации правильного доступа к данным/синхронизации и т.п.

Чего я не могу понять - это почему POSIX Threads/C code не страдает теми же проблемами, а наоборот есть "наиболее удобное сочетание для написания сложных мульитрединговых програм с элементами real-time".

[ link ]

Я понял, я понял. С++ - это как бы жид в мире языков программирования.

Успешен (но не по праву успешен). Презираем. Критикуем за грехи, коих не совершал. Но оправдания не помогают - ибо с ним всё равно всё понятно.

Примерно так.

Сам

avva тоже писал, что C++ плохой язык, а C хороший. И вот тут, хоть я и иначе ощущаю проблемы языка С++, по сути, а не по мелочам вряд ли можно возразить.

Хотя... вот интересно, если иметь всего две альтернативы: писать системы средней и большой сложности на С, или писать на С++ - выберет ли хоть кто-нибудь С? Ну да, выберет. Ведь уже сказано - "наиболее удобное сочетание для написания сложных мульитрединговых программ с элементами real-time".

Написал функциональность, позволяющую переходить с одного windows thread на другой в пределах одной функции.

( Read more... )

* Вот тут очень убедительно утверждается и соблазнительно описывается, что для concurrent программирования правильно использовать не семафоры, даже не conditional variables, а передачу сообщений. Крайне заинтригован. В своё время мне не хватило времени и желания разобраться с распределёнными алгоритмами (попадались черезчур математизированные книги с неясными перспективами практического использования изученного), но, похоже, непременно надо будет вернуться к теме.

* Cтрауструп написал дополнительное (современное) предисловие к "Design and Evolution of C++" http://www.research.att.com/~bs/DnE2005.pdf Излагает прошедшую историю с момента написания книги, текущий статус, возможные перспективы на ближайшие десять лет. К С++ у меня сейчас очень сложное отношение, но факт остается фактом - от этого языка я пока никуда не ушел, а для проектов, которыми я занимался последние лет десять, он был вполне адекватен, по большей части.

* Когда познакомился с Object-oriented, очень быстро обнаружил, что мыслю уже не на уровне алгоритмов, функциональностей или модулей, а на уровне классов. Вообще, было бы интересно подыскать какие-то задачи, примеры, где объектно-ориентированный подход не просто не очень удачен или проблематичен, но и в принципе уводит от более эффективного и адекватного решения.

Microsoft, оказывается, уже официально признал ненадёжность PulseEvent и призывает использовать вместо них conditional variables, которые наконец-то появились на Windows Vista.

Забавно, что cond-vars в исполнении Microsoft-a можно использовать не только с мютексами, но и... с read-write locks (которые microsoft тоже в vista имплементировал. Вообще, чего они там только не сделали, даже для создания синглтонов дают специальную функциональность).

Возвращаясь к cond-vars, непонятно, есть ли хоть какой-то смысл в их сочетании с read-write lock, помимо того, чтобы чуток больше быстродействия выжать в некоторых случаях экстремальной загрузки процессора. Упс... нет, пожалуй, уже понятно.

avva здесь зашел разговор, какие языки программирования стоит учить.

Жаль, но мне об этом особо нечего сказать. Всё пожрал ~~хомяк~~ C++.

До него учил я и APL и Forth и (не очень успешно, как сейчас понимаю) Lisp и Planner. После него - ничего. Лишь чтение Мейреса, Александреску и Саттера, шлифовка деревянного клинка. Про partial template specialisations прочитал где-то около 97-го года наверное, долго страдал от отсутствия поддержки оных в используемых компиляторах, потом и думать забыл об этом. Тем временем, мимо пролетели как boost (вот уж в чем, жаль, не удалось поучаствовать), так и C++0x.

http://groups.google.com/group/comp.programming.threads/browse_thread/thread/02fa00c87586643a/a68cce7bea2884bd#a68cce7bea2884bd

how resolve all the problems about threads (это название топика такое)
( Read more... )

тривиальная проблема с приемом проф-интервью (у программистов):

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

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

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

"Nearly All Binary Searches and Mergesorts are Broken"

"A bug can exist for half a century"

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

остальное тож повеселило:

"It is not sufficient merely to prove a program correct; you have to test it too."

Казалось бы, чудо произошло.

Начиная с Visual C++ 2005, внутри кода можно расставлять memory barriers, написав, к примеру, вызов intrinsic функции

_ReadWriteBarrier();

Мало того, в спецификацию volatile-типов добавлено долгожданное: операции над ними имеют семантику memory barriers.

И всё бы ничего, но ( Read more... )

Will you still need me, will you still feed me, when I'm sixty-four?

По поводу серии книг Саттера и вообще всей этой бучи GOW - следует задать вопрос, в какой степени обсуждаемые там вопросы действительно и объективно релевантны для программирования, а в какой отражают лишь малоудачные стороны дизайна широко используемо языка С++ и помимо этого ценности не имеют.

В Windows fункция InterlockedExchange (речь именно о ней, а не об InterlockedCompareExchange)
имплементирована через cmpxchg и цикл.
( Read more... )