Megérkezett a bsdsort a -CURRENT-be

FreeBSD

Nemrég volt szó arról, hogy egy új, BSDL-es sort variáns készül a FreeBSD-CURRENT-be Kövesdán Gábor és Oleg Moskalenko munkája nyomán. Akkor arról volt szó, hogy ha nem lesz ellenvetés vagy komolyabb hibáról beszámoló hibabejelentés, akkor a bsdsort megy a base rendszerbe, de addig a GNU sort lesz az alapértelmezett, amíg minden kétséget kizáróan bebizonyosodik, hogy a FreeBSD dobhatja a GNU sort-ot. Gábor a napokban bejelentette, hogy commit-olta a BSD sort-ot a -CURRENT-be. Egyelőre a GNU sort (sort) az alapértelmezett, a BSD sort pedig "bsdsort" néven érhető el. A bejelentés itt.

( tetra | 2012. 05. 17., cs – 14:01 )

Mit lehet az ilyen alapvető eszközökön annyit átírni/annyira máshogy újraírni, hogy már ne essen az eredeti licensz alá? Vagy hogy működik ez?
----
Hülye pelikán

elvileg ha nem láttad soha a GPL kódot, bezárkózol egy szobába, megírod a programot nulláról és a végeredmény pont ugyanaz lesz, akkor sem köt a GPL. persze erre semmi esély. Amúgy meg mindig lehet kísérletezni más algoritmusokkal, adatstruktúrákkal, sőt feladat szerint variálni is. még ilyen látszólag triviális programoknál is.

--------------------------------------
Unix isn't dead. It just smells funny.

Szo nincs arrol, hogy mashogy. Fuggetlenul is el lehet erni hasonlo eredmenyt. Bizonyitanod meg nem kell semmit, amig erre nem kernek. A bsdsort eseten egyebkent szvsz eleg nyilvanvalo a helyzet, hogy nem tortent masolas.

Es hogy catet hogy irsz meg maskepp? Lasd pl a dog nevu programot.

Lehet olyan catet irni ami mmapol (de ez nem fog mukodni ha olyat akarsz catelni, ami nem mmapolhato), lehet olyat ami karakterenkent olvassa vegig (ez lassu lesz), olyat ami blokkonkent (ez mar jobb, portabilis, stb), lehet ezeket kombinalni esszel (megprobalod mmapolni, ha nem megy, akkor meg open + read), lehet olyat irni ami httprol meg egyeb helyekrol is tud catelni, mert mondjuk valami VFS libet hasznal maga alatt (persze akkor /bin/cat -nak picit nagy lenne, dehat ez van!).

Lehet olyat irni, ami be tudja sorszamozni a sorokat, vagy olyat amiben ilyen nincs. Tudhat olyat, hogy a sorvegeket kiemeli, vagy az ures sorokat osszehuzza (es N darab ures sorbol mindig csak egyet mutat). Lehet olyat ami a TAB karaktereket ^I-vel jeloli.

Es meg sorolhatnam. Rengeteg lehetoseg rejlik egy kiscicaban.

--
|8]

Hát ha már a bsdsort-ról van szó, akkor néhány tipp. (Életemben meg nem néztem még semmilyen rendszer sort megvalósításának forrását, pedig lehetőségem lett volna rá.)
Eleve van egy halom különféle rendezőalgoritmus. (buborékendezés, heapsort, quicksort, beszúrórendezés, és í. t.) Melyiket használjuk? Ha sort programot akarnék írni, valószínűleg szétválasztanám két megoldásra: ha pipe-ból jön, akkor sima beszúró rendezéssel rendezném, hisz *elvben* amíg a másik program előállítja az adatot, addig én éppen rendezhetem magamban a már meglevő sorokat, így aztán mikor megérkezik az utolsó adatsor is, addigra már szépen rendezve van az összes addigi, tehát eléggé gyorsan kiköphetem a végső, rendezett adatokat. Míg ha nem pipeból, hanem seekelhető file-ból jön, akkor használnék valamilyen (a buboréknál és a beszúrónál) gyorsabb algoritmust.

Nyilván az se mindegy, hogy milyen adatszerkezeteket használva oldod meg a dolgokat. Nekem logikusnak tűnik, hogy valami láncolt listában legyenek az egyes sorokra mutató pointerek - és aztán persze ezeket a pointereket "rendezgessem", de elképzehető, hogy a tömbös tárolás bizonyos esetekben hatékonyabb - vagy akár az, hogy más ezt eleve kizárja, és teljesen mást tart jónak.

Nyilván lehet még kismillió egyéb olyan részt találni, amit a különböző fejlesztők különböző módon képzelnek el. Íly módon a megvalósítás is más és más lesz.

[bence@pc1 src]$ pwd
/home/bence/tmp/gnu/coreutils-8.17/src
[bence@pc1 src]$ 9 grep '(fork ?\(|pthread_)' *.c | cut -d: -f1 | uniq
install.c
sort.c
split.c
timeout.c

Ebből a sort pthread, a többiben fork van. (az nem tudom, multiprocess-nek számít-e)

--------------------------------------
Unix isn't dead. It just smells funny.

Van bármilyen unix-like base utility, amelyik erre fel van készítve? :)

A coreutils maintainer azt írta 2009. februárjában, hogy "we're currently starting to look at parallelism in gnu coreutils".

Itt van egy TODO lista a vége felé: http://www.pixelbeat.org/patches/coreutils/inbox_apr_2012.html

Ez még mindig azt mondja (persze ki tudja, friss-e), hogy "Possibly integrate the threaded external sort patch" (két levlistás linkkel).

A cilk-es kutatóktól láttam valamikor egy cikket a parallel merge-ről (vagyis amikor az összefuttatás is párhuzamosítva van). Most csak ezt találtam meg: http://en.wikipedia.org/wiki/Merge_sort#Parallel_processing

... Hm, de, megtaláltam. Ez az új link: http://software.intel.com/en-us/articles/free-download-multithreaded-al… ; "27.3 Multithreaded merge sort".

Kicsit szűkíti az algoritmusok terét, hogy:
1. Memóriánál nagyobb adatokat is rendezni kell
2. Az elterjedt háttértárak többsége szekvenciális olvasásnál hatékonyabb

Szóval ami első gondolatként adódik az valamilyen összefésüléses rendezés variáns, nem mintha ezt nem lehetne ezerféleképpen vagy kombinálva más algoritmusokkal...