Про IE

Открываю новую вкладку в IE7. По умолчанию стоит about:blank. Появляется новая вкладка, но работать с IE еще нельзя — довольно долго смотрю на красивое крутящееся колечко и надпись "Подключение..." За это время успеваю налить в кружку чай и поматериться на разработчиков.

Я не понимаю, почему нужно тратить столько времени на открытие пустой вкладки. Какое, нафиг, подключение? Куда? К about:blank? Я действительно не понимаю.

Цитата: Кериевски

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

Недавно мне порекомендовали книгу Джошуа Кериевски "Рефакторинг с использованием шаблонов". Очень понравилась. Толковый мужик, знает, о чем пишет. Как бы заполняет нишу между "Рефакторингом" Фаулера и "Шаблонами проектирования" Гаммы и его друзей.

Я позволю себе процитировать:

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

Книга, к тому же, издается за подписью Фаулера.

Слияние отсортированных массивов

Даны M отсортированных массивов по N элементов каждый. Необходимо слить их в одну отсортированную последовательность.

Есть несколько способов сделать это.

Первый способ - сливать сортированные последовательности по несколько штук (например, по две) до тех пор, пока не останется одна. Это и будет искомая последовательность. Например, для М=4, есть массивы М1, М2, М3 и М4 длиной по N элементов. На первом шаге сливаем M1 и М2, а потом М3 и М4. Получим два массива М5 и М6 длиной по 2*N элементов. На втором шаге сливаем М5 и М6 и получаем искомую последовательность длиной 4*N.

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

Вопрос в том, какой из способов более эффективный?

Можно попытаться посчитать приблизительное количество операций сравнения. Для простоты примем, что количество исходных массивов является степенью 2, то есть 2,4,8,... Для первого способа количество операций сравнения будет равно N*M*2*log₂M. А для второго - N*M².

Видно, что для М=2 или 4 количество операций будет одинаковое для обоих способов. А вот дальше количество операций для первого начнет уменьшаться. При М=32 соотношение количества операций будет примерно 1/3 в пользу первого способа.

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

Предположим, что памяти хватает только на обработку пары массивов. Следовательно, после обработки каждой пары массивов на любом шаге слияния, нам нужно сохранять на диск промежуточную последовательность, чтобы считывать ее на следующем шаге слияния. То есть, используя пример, нужно считать последовательности М1 и М2 и записать последовательность М5. Затем считать М3 и М4 и записать последовательность М6. Затем считать М5 и М6 и записать результирующий массив.

Если попробовать подсчитать, то получится, что на каждом шаге нужно считать М*N элементов и записать М*N элементов. При увеличении М количество шагов растет - K=log₂M. То есть количество операций чтения/записи будет равно 2*M*N*log₂M. А используя второй способ нужно считать и записать только 2*М*N элементов (потому, что для второго способа нужен только один шаг).

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

Освобождение памяти в std::vector

Я почему-то раньше был уверен, что выделенную память в std::vector можно освободить присваиванием:

typedef vector<int> int_vector;

int_vector v;
v.resize(10);
...
v = int_vector();

Оказалось, ошибался. Так не освобождает. По крайней мере, стандарт не обязывает.

Следовательно, остался только один способ освободить память — с помощью vector::swap:

int_vector().swap(v);


(способ описан в "Эффективном использовании STL" Скотта Мейерса)

Задачи на собеседованиях: шаблоны проектирования

Вот такие вопросы еще задают на знание паттернов проектирования.

Описать недостатки паттерна singleton. Предложить решения устранения недостатков.

GCC и precision loss

В процессе портирования нашего линуксового проекта на Windows обнаружилась интересная вещь: наш компилятор GCC не умеет распознавать ситуации с присвоением из long в short и им подобные. То есть, распознавать, скорее всего, умеет, а вот сообщать о них — нет.

Вот простой пример:

int main (int argc, char **argv)
{
  unsigned long a = 0xFFFFFFFE;
  unsigned char b = a + 1;
  return 0;
}

Я, честно говоря, был немало удивлен. Специально этим вопросом не занимался, но был уверен, что такие ситуации GCC отслеживать умеет. Ан нет... Что самое интересное, большинство моих знакомых гуру тоже были в этом уверены. В нашем проекте, как и во многих других, известных мне проектах, используется GCC 4.1.2, некоторые используют 4.2. Вроде бы есть опция -Wconversion, но работает она только для fixed и floating point. В общем, подстава.

Думаю, что о важности такого предупреждения говорить не нужно. В MSVC++ эта ситуация легко отслеживается включением третьего уровня предупреждений — /W3. После портирования нашего проекта на MSVC++, мы смогли легко локализовать и исправить несколько ошибок, связанных как раз с некорректным преобразованием типов.

Но самое интересное не в этом. После длительного изучения документации по GCC, все-таки нашел :)

Итак, не прошло и 25 лет, как разработчики GCC все таки прониклись пользой отслеживания размерности типов. Начиная с версии 4.3 (первый релиз вышел в марте 2008 года, то есть, всего полгода назад) GCC умеет распознавать и сообщать о ситуациях с присваиманием из long в char и им подобных.

Опция -Wconversion, которая работала только для fixed и floating point теперь разделена на две опции -Wtraditional-conversion и -Wconversion. Подробности можно почитать здесь http://gcc.gnu.org/wiki/NewWconversion

Я проверил — на приведенный пример ругается "warning: conversion to ‘short unsigned int’ from ‘long unsigned int’ may alter its value". Аллелуйа!

Ура, товарищи! Даешь новые версии! Даешь новые баги! :)

Задачи на собеседованиях: наследование в C++

Очередной вопрос с собеседования, который часто спрашивают.

У нас есть некая иерархия классов. Нам нужно запретить наследование от какого-то класса. В Java для этого есть специальное ключевое слово final, но в C++ такого слова нет. Попытка наследования от финального класса должна пресекаться на этапе компиляции.

Javascript: "option" object и IE

Простой скриптик. Берет все input-элементы с именем "hiddenlist" и заносит их в выпадающий список "selectlist". Отображаться в списке должно значение value, а на сервер отсылаться значение id. В Firefox работает, а в Internet Explorer 7 — нет.

var elems = document.getElementsByName("hiddenlist");

var selectobj = document.getElementById("selectlist");
removeAllChildren(selectobj);

for (i = 0; i < elems.length; ++i) {   var optobj = document.createElement("option");   optobj.value = elems[i].id;   optobj.text = elems[i].value;   selectobj.appendChild(optobj); }
Почему-то в IE после вызова appendObject(optobj) поле text очищается, или просто игнорируется. А поле optobj.value обрабатывается нормально. В результате в IE после вызова скрипта имею список из N пустых строк, но при этом на сервер отсылаются правильные значения.

Пришлось сделать так:

for (i = 0; i < elems.length; ++i) {   selectobj.appendChild(document.createElement("option"));   selectobj.options[i].value = elems[i].id;   selectobj.options[i].text = elems[i].value; }
В этом варианте работает в обоих браузерах. Мне, в общем-то, все равно, хотя второй вариант мне кажется менее приятным для глаз. Однако, непонятно почему первый вариант не работает в IE.

Exceptions и Visual C++

Недавно понадобилось собрать STL-проект на Visual C++ 2008 без использования исключений.

Почитал мануал по компилятору, долго игрался с настройками проекта и ключами /EHsc... Что-то никак не получается отключить исключения.

Наконец, залез в код STL и обнаружил там некий волшебный макрос _HAS_EXCEPTIONS. Добавление в опции компиляции ключа -D_HAS_EXCEPTIONS=0 привело к нужному результату — исключения в STL отключились.

Припоминаю, что лет шесть назад пытался решить эту же задачу для Visual C++ 6.0. И решалась она абсолютно таким же способом, через _HAS_EXCEPTIONS. Вот я и думаю, то ли Microsoft что-то перемудрил с Visual C++, то ли я его "готовить" не умею?..

С праздником вас, дорогие коллеги! С днем программиста! :)

Updated: Если нужно линковаться с msvcrt.lib или msvcrtd.lib (опции компилятора /MD или /MDd), то нужно определить еще один макрос:
#define _STATIC_CPPLIB

Updated: Вот интересная статья в тему http://ccollomb.free.fr/blog/?p=34

Задачи на собеседованиях: графы

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

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

UDP: Кстати, найдя кол-во узлов мы сможем ответить на общий вопрос о наличии цикла в графе. Иногда вопрос звучит именно так.

Как сменить shell

Тема не новая, но вот сегодня опять занимался решением старых проблем...

Не знаю кому как, но лично я считаю, что лучший shell — это bash. Не буду перечислять все преимущества, но одно просто неоспоримое — привык я к нему :) Я вообще люблю консоль, но bash — особенно. Он какой-то уютный, что ли.

Но вот сегодня захожу на очередной удаленный сервер по ssh и попадаю в ненавистный мне tcsh. Всё б ничего и можно потерпеть, но хочется уюта :) Но я здесь не root, и мне особо не рады. Что делать?

Исправляется довольно просто: нужно прописать смену shell в настроечном файле, который считывается при логине. Для tcsh этот файл называется .login и находиться должен в моей домашней папке. Если его нет, то нужно создать и прописать в нем следующее:

if (-f /bin/bash) then
  setenv SHELL /bin/bash
  exec /bin/bash --login
end if

Эти строки заменяют существующий shell, загружаемый по умолчанию, на bash. В данном случае по умолчанию был установлен tcsh.

В случае другого shell решение немного изменится. Например, если по умолчанию загружается sh, то никакой .login не поможет — sh просто не знает о существовании такого файла. Для sh нужно исправлять файл .profile (он тоже должен находиться в домашней папке):

if [ $SHELL = "/bin/sh" ]; then
  if [ -f /usr/bin/bash ]; then
    SHELL=/usr/bin/bash
    export SHELL
    exec /usr/bin/bash --login
  fi
fi

Маленький нюанс здесь — bash тоже считывает .profile и двойной if нужен здесь для того, чтобы исключить вероятность бесконечной рекурсии при загрузке bash.

Полный список соответствия разных shell'ов и настроечных файлов можно почитать здесь.

Блокирующие вызовы и ошибка EINTR

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

Функция sem_wait() уменьшает текущее значение семафора на 1. Если прежнее значение семафора было 0, то поток, выполняющий функцию sem_wait, блокируется до изменения значения семафора. При успешном выполнении — функция возвращает 0; при ошибке — вернет -1, а errno будет содержать код ошибки.

Вот пример неправильной обработки возвращаемого значения:

int res = sem_wait(&sem);
if (0 != res)
{
  // Ошибка!
  // Сообщаем об ошибке и выходим.
  ...
  return;
}

// Ошибки нет - продолжаем работу.
...


Что здесь неправильно? Дело в том, что функция sem_wait() является блокирующим системным вызовом. Поэтому выполнение этой функции может быть прервано, если выполняющийся поток получит какой-нибудь сигнал (например, сигнал о завершении другого потока). В этом случае функция вернет -1, а errno будет равна EINTR.

При этом никакой ошибки на самом деле нет, это просто способ дать программе обработать пришедший сигнал. Это необходимо учитывать, и вызов sem_wait() лучше всего делать в цикле. Например, таком:

int res;
do
{
  res = sem_wait(&sem);
}
while (0 != res && EINTR == errno);

if (0 != res)
{
  // Ошибка!
  // Сообщаем об ошибке и выходим.
  ...
  return;
}

// Ошибки нет - продолжаем работу.
...

Это касается и других блокирующих функций. Например, select, wait, waitpid и др. Возможность прерывания функции с ошибкой EINTR обычно описана в man'е.

Ошибки кодирования

Очередной багфиксинг показал, что за 30 лет мало что изменилось :)

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

И вот, модуль логгирования вдруг стал время от времени "падать" в совершенно непредсказуемые моменты. Оказалось, что виноват в этом один из компонентов, который вместо осмысленного текста посылает в модуль логгирования мусор. У компонента проблема, но почему модуль-то падает?..

Ошибка стара, как Си :) Разработчик модуля логгирования реализовал функцию примерно так:

void logMessage (const char *str)
{
  printf(str);
}

Видно ошибку? Проблема тут в том, что текст сообщения напрямую подается в функцию printf, минуя использование форматных строк типа "%s\n". Если подавать на вход функции осмысленный текст, то все будет хорошо, до тех пор пока в тексте сообщения не встретится "%s". В этом случае функция printf попытается сформировать новую строку, предполагая, что в стеке находятся дополнителльные аргументы. А аргументов-то там и нет. Вот тут-то printf и упадет с большой долей вероятности (скорее всего это произойдет, когда printf попытается вызвать strlen для значения, которое достанет из стека).

В нашем случае на вход функции подавался случайный мусор, поэтому время от времени в нем встречалась последовательность "%s", и модуль вываливался с ошибкой Segmentation fault.

Вот правильное использование printf для нашей функции логгирования:

void logMessage (const char *str)
{
  printf("%s", str);
}

Вызов printf и ей подобных должен выглядеть именно так и никак иначе.

Читать об уязвимостях printf.

Технологии мчатся вперед, а ошибки не меняются :)

Проблема импорта в Mozilla Thunderbird

Столкнулся сегодня с проблемой импорта почтовых сообщений из Microsoft Outlook в Mozilla Thunderbird 2.0.0.12.

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

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

После трехчасовой возни я все-таки выяснил, в чем дело :) Оказалось, что Антивирус Касперского мешает нормальной работе программы импорта. Я не знаю почему это происходит, и почему Касперский ничего не сообщал о том, что он там что-то блокировал, но факт налицо — после приостановки работы Касперского процедура импорта выполнилась без единой ошибки.

Цитата: Хаак

Бывший MVP (Most Valuable Professional – Самый Ценный Специалист) Microsoft Фил Хаак о повторных использованиях и обобщениях при разработке ПО

«Избегайте преждевременного обобщения», советует Хаак. «Не создавайте систему способную предсказать любое изменение. Пусть она будет достаточно гибкой для внесения изменений».

Чтобы определить, когда требуется обобщение, Хаак использует Правило Трех: «Когда вы в первый раз увидите, что что-либо может повторяться, не обобщайте это. В следующий раз сделайте все аналогичным способом, возможно даже при помощи копипастинга, но только не обобщайте. В третий раз хорошенько подумайте, как это можно обобщить».

Updated: Знакомство с Vim

По просьбе читателей поправил текст старой статьи "Знакомство с Vim. Настройки". Добавлено краткое описание режимов, а сам контент сделан более последовательным.

Еще раз об MDA

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

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

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

Как сделать merge в cleartool

В ClearCase сделать слияние (merge) для файлов с разных веток довольно просто. Проблемы начинаются, если на сливаемых ветках добавлялись или удалялись файлы. Оказывается, слияние директорий в ClearCase — задача непростая.

Выполнить слияние двух веток можно следующей командой:

cleartool findmerge . -fversion <version/label> -co -nc -merge -gmerge

Эта команда выполнит слияние с ветки version или label на текущую ветку для всех файлов, содержащих изменения. Ключ -gmerge удобно использовать при работе в графической среде — при возникновении конфликтов cleartool запустит визуальный инструмент для разрешения конфликтов вручную. Но при работе, например, по SSH, указывать этот ключ смысла не имеет; в этом случае используется консольный инструмент разрешения конфликтов. Тем, кто пользуется консольным, можно только посочувствовать.

Пример. У меня в текущей папке есть файлы file1, file2 и file3. На ветке /main/mybranch1 выполнены изменения для файлов file1 и file3. Чтобы слить изменения с ветки /main/mybranch1 на текущую ветку, мне необходимо выполнить команду:

cleartool findmerge . -fversion /main/mybranch1/LATEST -co -nc -merge -gmerge

В результате выполнения файлы file1 и file3 будут вычекнуты (checkout) на текущую ветку и модифицированы в соответствии с изменениями на ветке /main/mybranch1. Мне останется лишь выполнить checkin для измененных файлов. Файл file2 останется нетронутым.

Но вот, предположим, что на ветке /main/mybranch1 добавлен еще один файл — file4. Выполнение findmerge никак не коснется этого файла, потому что на текущей ветке этого файла нет. Значит, нужно сначала сделать merge для директории.

Описание команды merge говорит о том, что слияние директорий происходит в три шага:

1. убедиться, что на "той" ветке нет вычекнутых элементов;
2. вычекнуть директорию в текущей ветке;
3. выполнить команду cleartool merge для директории.

Только после этого можно будет безболезненно выполнить cleartool findmerge.

Итак, синхронизируем текщую директорию с веткой /main/mybranch1:

ct co -nc .
ct merge -to ./ ./@@/main/mybranch1/LATEST
  Added file file4 to ./.

Теперь можно зачекать измененную директорию (а можно сделать это потом). И наконец-то можно выполнить долгожданный findmerge:

cleartool findmerge . -fversion /main/mybranch1/LATEST -co -nc -merge -gmerge

Будет выполнено слияние для файлов file1, file3 и file4. Теперь нужно внести в репозиторий результаты слияния веток. Заносим всё сразу — зачем мелочиться? :)

ct ci -c "Merged from /main/mybranch1." `ct lsco -r -cview -short`

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

Цитата: Papadimoulis

Alex Papadimoulis о разработке корпоративного ПО (" Avoiding Development Disasters")

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

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

Грамотно спроектированная система, созданная на протяжении последних восьми–десяти лет не требует масштабной модернизации.

Использование OSS в своих разработках

В очередной раз пересортировывал гигабайты статей и заметок, собранных на моем жестком диске, и наткнулся на текстовый файл с некоторыми правилами использования Open Source Software в своих разработках. Думаю, здесь этой заметке самое место.

Когда ваш продукт обязан быть Open Source

- если вы изменяли чужой GPL-код или исправляли в нем ошибки;
- если расширяли функциональность GPL-кода добавляя свой код;
- копировали фрагменты кода из GPL-продуктов в свой код;
- использовали заголовочные файлы из GPL-кода;
- статическая линковка вашего кода с GPL-кодом или LGPL;
- динамическая линковка с GPL-библиотеками или LGPL;


Когда ваш продукт не обязан быть Open Source

- при использовании GCC для компиляции вашего кода;
- при использовании открытых стандартов (HTTP, TCP/IP, SOAP, POSIX и т. д.);
- при взаимодействии вашей программы с OSS с помощью командной строки, пайпов или сокетов;
- при использовании архитектуры ПО, изолированной от OSS.