"exec" на виндовсу

Једна стара белешка:

"еxec" у мајкрософтовој "C" библиотеци не ради исто као на посикс системима. У мајкрософтовој имплементацији ова функција креира нови процес који наслеђује "handles", oтворене фајл дескрипторе и слично, али добија нови број процеса (process id).

Тако програм који "рачуна" на нормално понашање ове функције може да мисли да је процес који је креирао већ завршио иако се то није стварно догодило. На пример, грешка која се десила у пракси је да је један скрипт стартовао апликацију која је користећи "exec" требало да направи нови процес, а скипт је у међувремену чекао да се оригинални процес који је креирао заврши. Међутим, виндовс би вратио контролу скипрти тако да изгледа као да се креирани програм завршио, али у стварности нови процес са новим бројем процеса би наставио да ради.

Поправка се састојала у замени "exec" позива у поменутој апликацији са "spawn" и затим чекања новокреираног процеса из саме апликације, па тек онда изласка како би скрипт могао да настави да чека само на апликацију.

elif евалуација

Интересантна промена се десила у gcc Ц препроцесору. Евалуација elif гране препроцесорске директиве "if" се извршава чак и ако је услов дат у if задовољен.

Конкретан пример:

#ifdef
#ifndef FOO_BAR
#define FOO_BAR
#elif FOO_BAR == 0
#endif

Ово ради без проблема на претходним верзијама, на пример 4.3.3 али не и на 4.4.1. Не знам у којој тачно верзији је дошло до промене, али ево извештаја проблема: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36320

Исправна конструкција горе наведеног примера би била:

#ifdef
#ifndef FOO_BAR
#define FOO_BAR 1
#elif FOO_BAR == 0
#endif

Секвентна тачка

Односно "Sequence point".

Питање у вези секвентне тачке (ако сам превео добро) често долази на разговорима за посао. Многи нису свесни шта је то иако је у суштини проста ствар. Пре неки дан ме на то потсетио бивши колега, а и ја сам то питање добио на мом разговору.

Секвентна тачка је синтаксни елемент дефинисан језиком који гарантује да ће споредни ефекти евалуације израза са леве стране таквог елемента гарантовано бити завршени пре него што започне евалуација израза са десне стране.

На пример, у Цеу и Це++ то је оператор зарез ',' али не и аримтетички оператори. Осим зареза, има још секвентних тачака као што су '?' и логички оператори.

Кратак, али добар текст се може наћи на википедији.

Решавање судоку

Прошле године су нам у посети били моји родитељи и при том сам сазнао да је мој отац постао пасионирани играч судоку. Мало сам играо и ја, врло интересантна мозгалица. Природно, дошао сам на идеју да решавање "аутоматизујем". У то време сам учио "Scheme" језик - шема ме још занима али се нема времена.

Ипак, склепао сам некакав програмчић а ових дана га пречистио и проверио. Програм следи у целини.

Програм је развијан и тестиран коришћењем "Petite Chez Scheme" http://www.scheme.com/petitechezscheme.html.

; Решавање судоку матрице.
; Функција за решавање је:
; (solve sudo azbuka)
; где је sudo низ који описује почетно
; стање судоку, а azbuka низ који дефинише
; могуће елементе. Класичан судоку ће
; у азбуци имати цифре 1 до 9.


;
; Дефиниција примера судоку проблема
; Судоку таблица се задаје као низ
; по редовима.
;
; Редови и колоне су нумерисане
; бројевима 1 до 9.
;
; Непознати елементи су задати елементом
; који није садржан у азбуци. У примеру
; који следи, елементе које сам хтео да
; прогласим непознатим сам обележио подвлаком.
;
; Резултат обележава решене елементе
; заградом (под листа). Уколико
; једнозначно решење није нађено,
; у загради ће бити изслитана могућа
; решења.
;
(define sudo '(  _1  2 _3  4  5  6 _7 _8 _9
                  4 _5  6  7 _8 _9  1  2  3
                 _7 _8 _9 _1  2  3 _4 _5  6
                  2  3 _4  5  6  7 _8 _9  1
                 _5  6  7 _8 _9  1  2  3  4
                 _8 _9  1  2  3  4  5  6  7
                 _3  4  5  6 _7 _8 _9  1  2
                 _6  7 _8 _9  1  2  3  4  5
                 _9 _1  2  3 _4  5  6 _7  8   ))


;
; Азбука.
; Азбука може бити произвољна све док задовољава
; услов да је број елемената једнак квадрату
; целобројног позитивног броја.
;       
(define azbuka '(1 2 3 4 5 6 7 8 9))

(define a2 '(0 1 2 3))
(define s2 '( ? 1 2 3
              3 2 1 ?
              1 3 0 2
              2 0 ? 1))
              


;
; Основна функција за решавање судоку.
;
(define (solve sudo azbuka)
    (solve1 sudo azbuka 0))

; 
; Помоћна функција за решавање
;
(define (solve1 sudo azbuka rc)
    (cond
   ((>= rc (* (list-len azbuka) (list-len azbuka))) sudo)
      (else
        (solve1
          (append 
            (front (reduce sudo azbuka) rc)
            (cons
              (possible (reduce sudo azbuka) azbuka (row-idx azbuka rc) (col-idx azbuka rc))
              (skip-n (reduce sudo azbuka) (1+ rc))))
          azbuka
          (1+ rc)))))



;
; Редукуј све непознате чланове на листе могућих
; решења
;
(define (reduce sudo azbuka)
 (reduce1 sudo azbuka 0))

;
; Помоћна функција.
; Редукуј све непознате чланове на листе могућих
;
(define (reduce1 sudo azbuka rc)
 (cond
  ((> (1+ rc) (* (list-len azbuka) (list-len azbuka))) '())
  (else
   (cons
    (possible sudo azbuka (row-idx azbuka rc) (col-idx azbuka rc))
    (reduce1 sudo azbuka (1+ rc))))))


;
; Помоћна функција - број елемената у 
; датој листи.
;
(define (list-len lst)
    (cond
      ((or (null? lst) (is-atom? lst)) 0)
      (else
        (1+ (list-len (cdr lst))))))
        
; 
; Помоћна функција - израчунава димензију под-судоку
; матрице.
;
(define (koren azbuka) (sqrt (list-len azbuka)))
                                                                     
;                                                                    
; Одређивање природе вредности aorl
; Враћа #f уколико дата вредност није
; атом.
;
(define is-atom? atom?)

;(define (is-atom? aorl)
;    (cond
;      ((or 
;           (list? aorl)
;           (not (number? aorl))) #f)
;      (else (atom? aorl))))

; 
; Да ли је дати елемент слово азбуке
;
(define (member? at lst)
 (cond
  ((null? lst) #f)
  (else
   (or (eq? at (car lst))
    (member? at (cdr lst))))))

;
; Да ли је дата вредност задата?
;
(define (is-given? aorl azbuka)
    (and (is-atom? aorl) (member? aorl azbuka)))

;
; Да ли је вредност решена?
;
; Решена је само онда када је представљена
; листом са тачно једним елементом који
; није 0.
;
(define (is-solved? lat azbuka)
    (cond
      ((eq? 1 (list-len lat)) #t)
      (else (is-given? lat azbuka))))

;
; Помоћна функција - број елемената у 
; датој листи.
;
(define (list-len lst)
    (cond
      ((or (null? lst) (is-atom? lst)) 0)
      (else
        (1+ (list-len (cdr lst))))))

;
; Прескочи n елемената и врати
; n-ти елемент.
;
(define (skip-n sudo n)
    (cond
      ((null? sudo) '())
      ((eq? 0 n) sudo)
      (else
        (skip-n (cdr sudo) (1- n)))))

;
; Врати листу од n елемената почев од
; датог елемента sudo
;
(define (front sudo n)
    (cond
      ((null? sudo) '())
      ((eq? 0 n) '())
      (else
        (cons (car sudo) (front (cdr sudo) (1- n))))))

;
; Издвој ред n
; 
(define (row sudo azbuka n)
    (cond
      ((null? sudo) '())
      (else
        (front (skip-n sudo (* (1- n) (list-len azbuka))) (list-len azbuka)))))

;
; Помоћна функција за издвајање колоне
;
(define (getcol sudo azbuka n)
    (cond
      ((null? sudo) '())
      ((eq? 0 n) '())
      (else
        (cons (car sudo) (getcol (skip-n sudo (list-len azbuka)) azbuka (1- n))))))

;
; Издвоји колону n
;
(define (col sudo azbuka n)
    (cond
      ((null? sudo) '())
      (else
        (getcol (skip-n sudo (1- n)) azbuka (list-len azbuka)))))
       
;
; помоћна функција - врати ред (почев од 1)
; на основу датог индекса листе која дефинише
; судоку. Индекс почиње са 0.
; 
(define (row-idx azbuka idx)
 (1+ (floor (/ idx (list-len azbuka)))))
 
;
; помоћна функција - врати колону (почев од 1)
; на основу датог индекса листе која дефинише
; судоку. Индекс почиње са 0.
; 
(define (col-idx azbuka idx)
 (1+ (- idx (* (1- (row-idx azbuka idx)) (list-len azbuka)))))

;
; Помоћна функција за издвајање "мини судоку" односно
; подматрице
;
(define (sub-sudo-row sudo azbuka r c rn koren)
 (cond 
  ((> rn koren) '())
  ((null? sudo) '())
 (else
  (append
   (front (skip-n (row sudo azbuka (+ rn (* (1- r) koren))) (* (1- c) koren)) koren)
   (sub-sudo-row sudo azbuka r c (1+ rn) koren)))))

;
; Издвој мини судоку (a пута a, где је а корен
; броја елемената у азбуци) са задате позиције.
; Позиције мини судоку су нумерисане 1 до (list-len azbuka).
;
(define (sub-sudo sudo azbuka r c)
 (sub-sudo-row sudo azbuka r c 1 (koren azbuka)))

;
; 
;
(define (extract-solved su azbuka)
    (cond
      ((null? su) '())
      ((is-solved? (car su) azbuka) 
    (cons 
  (cond
    ((list? (car su)) (caar su))
    (else
    (car su)))
    (extract-solved (cdr su) azbuka)))
      (else
        (extract-solved (cdr su) azbuka))))

;
; Разлика две судоку
;
(define (diff su lat)
    (cond
      ((null? su) '())
      ((null? lat) su)
      ((member? (car su) lat) (diff (cdr su) lat))
      (else
        (cons (car su) (diff (cdr su) lat)))))

;
; Да ли је вредност at члан низа lat?
;
(define (member? at lat)
    (cond
      ((null? lat) #f)
      ((eq? at (car lat)) #t)
      (else
        (member? at (cdr lat)))))

;
; Врати сва немогућа решења за дату позицију.
; (сви елементи азбуке који су већ дати или
; нађени у датом реду, колони и под судоку).
;
(define (allsolved sudo azbuka r c)
    (append
      (extract-solved (row sudo azbuka r) azbuka)
      (extract-solved (col sudo azbuka c) azbuka)
      (extract-solved 
  (sub-sudo 
   sudo azbuka (ceiling (/ r (koren azbuka))) (ceiling (/ c (koren azbuka))))
  azbuka)))


;
; Врати листу могућих решења за дати елемент.
; 
(define (possible sudo azbuka r c)
    (cond
      ((is-solved? (element sudo azbuka r c) azbuka)
       (element sudo azbuka r c))
      (else
        (diff azbuka (allsolved sudo azbuka r c)))))

;
; Помоћна функција. Врати дати елемент.
; Ред и колона почињу од 1
;
(define (element sudo azbuka r c)
    (car (skip-n sudo (+ (* (list-len azbuka) (1- r)) (1- c)))))

gcc и груписање функција

У неким ретким случајевима, потребно је оптимизовати програм тако да се смањи растојање између функција које се често позивају. Могући добитак од овакве оптимизације је смањење "TLB misses" односно потребе да процесор учитава податке за превођење виртуелне у физичку адресу за дати блок. Друга могућа добит је искоришћење различитих нивоа кеширања: уколико су функције физички близу, велика је вероватноћа да ће, док се прва извршава, друга бити учитана у кеш.

Конкретан пример који имам је оптимизација кода за "лењо разрешавање" адреса симбола у динамички повезаним програмима (lazy binding).

Наш оперативни систем (QNX Neutrino) има динамичко повезивање, али не "уме" да то уради "лењо" односно на захтев. Како сада ради, наш динамички повезивач разрешава све адресе симбола на самом почетку, пре него што програм стигне у "main". Последњих неколико дана сам радио на имплементацији која већ постоји на већини јуникс система, а која подразумева разрешавање симбола функција у тренутку првог позива.

Како између два разрешења може доста кода да се изврши, велика је вероватноћа да ће функције потребне за лењо разрешење већ бити избачене из кеша, а такође из процесорске табеле за превођење адреса (TLB) избачене ставке које се односе на физичке странице меморије у којима су те функције. Груписањем функција тако да буду близу једна другој, идеално у једној физичкој страници меморије, ће смањити број промашаја.

Приликом прве компилације установио сам да су функције на приличном растојању једна од друге. Конкретно, приликом дисасемблирања објектног фајла, добио сам ово:

bind_func     0x000000cc
 resolve_func  0x000029e0
 resolve_rels  0x00001010
 lookup_global 0x00000c68

Види се да би фунције биле распоређене у бар 3 меморијске странице (под условом да је страница 4KiB).

Да бих груписао исте, искористио сам атрибут фунције "hot" уведен са gcc верзијом 4.3. Горе наведеним функцијама сам у декларацију додао: __attribute__((hot)). Gcc тако означене функције оптимизује агресивније али и групише у посебну секцију ".text.hot". На крају процеса повезивања, функције су распоређене једна до друге:

bind_func    0x0003f3f8
 resolve_rels 0x0003f418
 resolve_func 0x0003f88c

Интересантно је да је lookup_global "нестала" односно апсорбована у функције које је позивају.

У сваком случају, уместо 4 физичке странице сада функције могу да стану у само једну и распоређене су једна уз другу чиме се повећава шанса да у тренутку позива већ буду у кешу.


Тек треба да упоредим да ли се овиме добија нешто што може да се измери. Вероватно ће доста зависити од процесора па и самог уређаја.

7-zip

Коначно сам инсталирао 7-zip (http://www.7-zip.org/) и код куће. Већ неколико месеци га користим на послу. 7-zip "разуме" различите формате архива, између осталих .zip, .rar, .bz2...

WinZip ми стварно неће недостајати.

"Безбедне" Ц функције за манипулацију текста

Често се нађем у ситуацији да нисам сигуран да ли одређена ц функција за манипулацију текста (snprintf, strncpy, strncat, ...) исписује тачно "n" карактера, да ли резултирајући стринг завршава нулом итд.

Ради лакшег потсећања, ево примера за сваку од функција:

#include <stdio.h>
#include <string.h>

static void koristi_snprintf(const char *const tekst)
{
    char buf[10];

    snprintf(buf, sizeof(buf)/sizeof(buf[0]), "%s", tekst);
    /* Текст који смо добили у buf је можда скраћен, али је коректан са
     * нулом на крају. */
    printf("%s\n", buf);
}


static void koristi_strncpy(const char *const iz)
{
    char u[10];
    const unsigned s = sizeof(u)/sizeof(u[0]);

    strncpy(u, iz, s - 1);
    u[s - 1] = '\0'; /* Морамо ручно да завршимо стринг. */

    printf("%s\n", u);
}


static void koristi_strncat(const char *const tekst)
{
    char buf[10];
    const unsigned s = sizeof(buf)/sizeof(buf[0]);

    strncpy(buf, "12345", s - 1);
    buf[s - 1] = '\0';

    /* Број карактера који функција може да дода је мања за један
     * због завршне нуле и мања за дужину стринга који је већ у
     * баферу. */
    strncat(buf, tekst, s - 1 - strlen(buf));
    printf("%s\n", buf);
}


static void koristi_strncmp(const char *const tekst)
{
    const char buf[] = "12345";
    const unsigned s = sizeof(buf)/sizeof(buf[0]);

    if (strncmp(buf, tekst, s) == 0)
 printf("Prvih %d karaktera su isti\n", s);
    else
 printf("Razlika postoji u prvih %d karaktera\n", s);
}



int main()
{
    koristi_snprintf("Zdravo. Ovaj tekst je predugacak.");
    koristi_strncpy("Zdravo. Ovaj tekst je predugacak.");
    koristi_strncat("Zdravo. Ovaj tekst je predugacak.");
    koristi_strncmp("12345678");
    return 0;
}