*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

вторник, 24 мая 2011 г.

Безопасный sizeof для массивов в С++

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

Например, это можно слелать так:

#define arraysize(array) (sizeof(array) / sizeof(array[0]))

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

Вчера прочитал на Харбе (кстати, отличная статья), что в С++ можно сделать этот макрос более безопасным.

Вот код, который используется в Chrome:

template <typename T, size_t N>
char (&ArraySizeHelper(T (&array)[N]))[N];
#define arraysize(array) (sizeof(ArraySizeHelper(array)))

Выглядит немного запутанно, но можно разобраться:

  • T (&array)[N] - определение массива (T array[N]), который передается по ссылке
  • char (&ArraySizeHelper(...)[N] - функция, возвращающая массив по ссылке
  • sizeof(ArraySizeHelper(array)) - определение размера возвращаемого функцией значения
  • Все это шаблон функции, параметризированный типом массива и его размером, который автоматически определяется компилятором при раскрытии шаблона. Так как функция реально не вызывается, то и тело ее определять не нужно.

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

Кстати, можно поиграться с sizeof() от типа возвращаемого функцией значения:

#include <iostream>
#include <string>

std::string f() {
  return std::string();
}

int main() {
  std::cout << sizeof( (&f)() ) << std::endl;
  std::cout << sizeof( std::string ) << std::endl;
  return 0;
}

У меня на VS2010 выводит два раза число "28".

Интересно, что в чистом С такой номер тоже проходит:

#include <stdio.h>

struct t {
  char x[1024];
};

struct t f() {
  struct t a;
  return a;
}

int main() {
  printf("%d\n", sizeof(struct t));
  printf("%d\n", sizeof( (*f)() ));
  return 0;
}

Печатает два раза "1024".

понедельник, 23 мая 2011 г.

Количество пересечений в двудольном графе

Это очередной пост из серии "записки дилетанта о спортивном программировании". Тут как в том анекдоте: "Лев Толстой очень любил играть на балалайке, но не умел. Порой пишет очередную главу, а сам думает: тренди-бренди, тренди-бренди...". В общем, точно про меня и спортивное программирование.

Итак, задача с крайне простой постановкой.

Дан произвольный двудольный граф: "n" вершин слева, "m" справа и некоторое количество дуг. Требуется ответить на вопрос: сколько раз дуги графа пересекаются.

В данном примере n=5, m=4, десять дуг: 1-1, 1-2, 2-1, 2-2, 3-3, 4-1, 4-3, 5-1, 5-2, 5-4, количество пересечений: 10.


Факт пересения рассматривается всегда попарно. Например, если уж так случилось, и три дуги пересекаются в одной геометрической точке, формально пересечений все равно три, а не одно.

Задача имеет решение за O(n*m).

воскресенье, 22 мая 2011 г.

Индексация по строковой константе

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

#include <stdio.h>

int main() {
  int i;
  for (i = 0; i < 8; ++i)
    printf("%c", "12345678"[i]);
  printf("\n");
  return 0;
}

Лично мне выражение "12345678"[i] как-то режет глаз. Хотя с точки зрения языка тут все в порядке.

вторник, 17 мая 2011 г.

Эмулятор x86 на JavaScript, на котором работает Linux

Установите свежий браузер (FF4 или Chrome 11) и просто сходите по указанной ссылке.

http://bellard.org/jslinux/

Посмотрите, как прямо в вашем браузере загрузится Linux. Запустите ls, top, emacs, vi, df, ifconfig, ping и т.д. Попробуйте скомпилировать и запустить программу "tcc hello.c && ./a.out".

А теперь осознайте - это все чистая программная эмуляция x86 (подробности).

Мой эмулятор Intel 8080 и Радио-86РК просто ничто, по сравнению с этим.

У меня до сих пор небольшой шок от увиденного.

Когда-то я был уже удивлен до глубины души одним из проектов (Загрузка Linux без ядра за 25 секунд) этого товарища, но это...

понедельник, 9 мая 2011 г.

Ссылки на файлы и каталоги в Windows

К своему стыду я думал, что Windows все еще существует в прошлом веке без возможности делать ссылки на файлы в файловой системе. Я знал про ссылки на каталоги (junctions), которые можно делать, например, в FAR'е через Alt-F6.

Но сегодня, открыв "Windows Internals" в случайном месте, наткнулся на параграф про данный вопрос.

Итак, просто привожу небольшой лог с консоли (Windows 7).

ver

Microsoft Windows [Version 6.1.7601]

Создаем файл и каталог:

cd C:\Temp\links
C:\temp\links>mkdir folder
C:\temp\links>echo >file

Создаем символьную ссылку на каталог:

C:\temp\links>mklink /D link1 folder
symbolic link created for link1 <<===>> folder

Создаем junction на каталог (на файл его создать нельзя):

C:\temp\links>mklink /J link2 folder
Junction created for link2 <<===>> folder

Создаем символьную ссылку на каталог немного иначе:

C:\temp\links>mklink link3 folder
symbolic link created for link3 <<===>> folder

Создаем символьную ссылку на файл:

C:\temp\links>mklink link4 file
symbolic link created for link4 <<===>> file

Результат:

C:\temp\links>dir
 Volume in drive C has no label.
 Volume Serial Number is C021-6C9F

 Directory of C:\temp\links

09/05/2011  18:26    <DIR>          .
09/05/2011  18:26    <DIR>          ..
09/05/2011  18:26                13 file
09/05/2011  18:25    <SYMLINKD>     link1 [folder]
09/05/2011  18:25    <JUNCTION>     link2 [C:\temp\links\folder]
09/05/2011  18:25    <SYMLINK>      link3 [folder]
09/05/2011  18:26    <SYMLINK>      link4 [file]
09/05/2011  18:23    <DIR>          folder
               3 File(s)             13 bytes
               5 Dir(s)  208,278,925,312 bytes free

Обратите внимание на интересные типы файлов: <SYMLINKD>, <JUNCTION>, <SYMLINK>. Как написано в книге, первые два по функциональности одно и то же, просто <JUNCTION> более старый механизм, доступный в более старых версиях Windows и который поддерживает ссылки только внутри одного тома.

Также, обратите внимание, что ссылка "link3" хоть и является ссылкой на каталог, не работает нормально как обычный каталог (в отличие от "link1" и "link2", которые в целом ведут себя как нормальне каталоги). FAR, кстати, тоже, "link3" за каталог не считает.

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

И книга, "Windows Internals", чертовски хороша, рекомендую.

пятница, 6 мая 2011 г.

Видео докладов с ACCU 2011

Увы, приходится давать просто ссылки, ибо не дают вставлять код для просмотра прямо со страницы.

Скотт Мейерс

CPU caches and why you care

Move semantics, perfect forwarding, and rvalue references

Джон Лакос (Блумберг)

Defensive programming done right

Диетмар Кул (Блумберг)

Generic Programming with C++ 0x

Остальные видео тоже доступны.

среда, 4 мая 2011 г.

Кто быстрее: memset vs bzero vs std::fill

У нас тут идет второй день тренинг по С++ и unit-тестированию. Ведет Kevlin Henney. Отличный дядка.

Все как обычно -- стараемся приучать к культуре разработки через тесты, ну и попутно склонить патриотов С к С++, убедив их, что на С++ можно таки писать также эффективно, как и на С. Да еще и в разы быстрее.

Зашла тема про std::fill(). Я вставил словечко, что мол fill() работает также быстро как и memset(), так как он используется в fill() для простых типов.

Написали программу, в которой есть интересный момент.

#include <cstdlib>
#include <algorithm>

int main(int argc, char* argv[]) {
  int mode = argc > 1 ? std::atoi(argv[1]) : 1;
  int n = 1024 * 1024 * 1024 * 1;
  char* buf = new char[n];
  if (mode == 1)
    std::memset(buf, 0, n * sizeof(*buf));
  else if (mode == 2)
    bzero(buf, n * sizeof(*buf));
  else if (mode == 3)
    std::fill(buf, buf + n, 0);
  else if (mode == 4)
    std::fill(buf, buf + n, '\0');
  return buf[0];
}

Обратите внимание на ветки 3 и 4. Они почти одно и то же, но не совсем.

В целом была мысль получить вот эту специализацию fill():

// Specialization: for one-byte types we can use memset.
inline void
fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
{
  __glibcxx_requires_valid_range(__first, __last);
  const unsigned char __tmp = __c;
  std::memset(__first, __tmp, __last - __first);
}

Итак, Makefile:

all: build run

.SILENT:

target = memset_bzero_fill

build:
        g++ -O3 -o $(target) $(target).cpp

run: run-memset run-bzero run-fill-1 run-fill-2

go:
        (time -p ./$(target) $(mode)) 2>&1 | head -1 | cut -d' ' -f 2

run-memset:
        echo $@ `$(MAKE) go mode=1`

run-bzero:
        echo $@ `$(MAKE) go mode=2`

run-fill-1:
        echo $@ `$(MAKE) go mode=3`

run-fill-2:
        echo $@ `$(MAKE) go mode=4`

Компилятор "gcc version 4.2.1 (Apple Inc. build 5666) (dot 3)".

Запускаем:

run-memset 1.47
run-bzero 1.45
run-fill-1 1.69
run-fill-2 1.42

Видно, как ветка 3 (run-fill-1) значительно тормозит, по сравнению с 4, хотя разница всего в типе последнего параметра - 0 и '\0'.

Смотрим ассемблер:

(gdb) disass main
Dump of assembler code for function main:
0x0000000100000e70 <main+0>:    push   %rbp
0x0000000100000e71 <main+1>:    mov    %rsp,%rbp
0x0000000100000e74 <main+4>:    push   %r12
0x0000000100000e76 <main+6>:    push   %rbx
0x0000000100000e77 <main+7>:    dec    %edi
0x0000000100000e79 <main+9>:    jle    0x100000ec3 <main+83>
0x0000000100000e7b <main+11>:   mov    0x8(%rsi),%rdi
0x0000000100000e7f <main+15>:   callq  0x100000efe <dyld_stub_atoi>
0x0000000100000e84 <main+20>:   mov    %eax,%r12d
0x0000000100000e87 <main+23>:   mov    $0x40000000,%edi
0x0000000100000e8c <main+28>:   callq  0x100000ef8 <dyld_stub__Znam>
0x0000000100000e91 <main+33>:   mov    %rax,%rbx
0x0000000100000e94 <main+36>:   cmp    $0x1,%r12d
0x0000000100000e98 <main+40>:   je     0x100000eac <main+60>   ; mode == 1
0x0000000100000e9a <main+42>:   cmp    $0x2,%r12d
0x0000000100000e9e <main+46>:   je     0x100000eac <main+60>   ; mode == 2
0x0000000100000ea0 <main+48>:   cmp    $0x3,%r12d
0x0000000100000ea4 <main+52>:   je     0x100000ed2 <main+98>   ; mode == 3
0x0000000100000ea6 <main+54>:   cmp    $0x4,%r12d
0x0000000100000eaa <main+58>:   jne    0x100000ebb <main+75>   ; mode != 4 -> выход

; Реалиазация через memset().

0x0000000100000eac <main+60>:   mov    $0x40000000,%edx        ; mode = 1, 2 или 4
0x0000000100000eb1 <main+65>:   xor    %esi,%esi
0x0000000100000eb3 <main+67>:   mov    %rbx,%rdi
0x0000000100000eb6 <main+70>:   callq  0x100000f0a <dyld_stub_memset>

0x0000000100000ebb <main+75>:   movsbl (%rbx),%eax             ; выход
0x0000000100000ebe <main+78>:   pop    %rbx
0x0000000100000ebf <main+79>:   pop    %r12
0x0000000100000ec1 <main+81>:   leaveq
0x0000000100000ec2 <main+82>:   retq

0x0000000100000ec3 <main+83>:   mov    $0x40000000,%edi
0x0000000100000ec8 <main+88>:   callq  0x100000ef8 <dyld_stub__Znam>
0x0000000100000ecd <main+93>:   mov    %rax,%rbx
0x0000000100000ed0 <main+96>:   jmp    0x100000eac <main+60>

; Реализация на обычных командах.

0x0000000100000ed2 <main+98>:   movb   $0x0,(%rax)             ; mode = 3
0x0000000100000ed5 <main+101>:  mov    $0x1,%eax
0x0000000100000eda <main+106>:  nopw   0x0(%rax,%rax,1)
0x0000000100000ee0 <main+112>:  movb   $0x0,(%rax,%rbx,1)
0x0000000100000ee4 <main+116>:  inc    %rax
0x0000000100000ee7 <main+119>:  cmp    $0x40000000,%rax
0x0000000100000eed <main+125>:  jne    0x100000ee0 <main+112>

0x0000000100000eef <main+127>:  movsbl (%rbx),%eax             ; выход
0x0000000100000ef2 <main+130>:  pop    %rbx
0x0000000100000ef3 <main+131>:  pop    %r12
0x0000000100000ef5 <main+133>:  leaveq
0x0000000100000ef6 <main+134>:  retq

Видно, что благодаря оптимизации, ветки 1, 2 и 4 реализованы одинаково - через memset(). Вызов fill() в ветке 4 удалось свести к memset().

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

Неверный тип нуля не дал компилятору правильно выбрать специализацию шаблона.

Мораль? И мораль тут не очень хорошая.

Мне кажется, что количество людей, которые напишут "std::fill(buf, buf + n, 0)", разительно больше, чем "std::fill(buf, buf + n, '\0')".

А разница весьма существенна.

Посты по теме: