Prosíme přihlašte se nebo zaregistrujte.

Přihlašte se svým uživatelským jménem a heslem.

Autor Téma: Alokace velkého globálního pole  (Přečteno 3532 krát)

Royal

  • Návštěvník
  • *
  • Příspěvků: 31
    • Zobrazit profil
Alokace velkého globálního pole
« kdy: 12 Duben 2011, 19:48:27 »
Čest práci všem,

mám problém s `ld`.
Když kompiluju program, ve kterém mám pole s velkým rozměrem (nebo vícerozměrné pole), `ld` alokuje paměť jako bláznivé.
To mě zas tak netrápí. Jen mě trápí následující hlášky:

Kód: [Vybrat]
/tmp/ccKJwOsb.o: In function `main':
***.c:(.text+0x1d5): relocation truncated to fit: R_X86_64_32 against symbol `***' defined in COMMON section in /tmp/ccKJwOsb.o
***.c:(.text+0x215): relocation truncated to fit: R_X86_64_PC32 against symbol `***' defined in COMMON section in /tmp/ccKJwOsb.o
***.c:(.text+0x409): relocation truncated to fit: R_X86_64_PC32 against symbol `***' defined in COMMON section in /tmp/ccKJwOsb.o
collect2: ld returned 1 exit status

Kdesi jsem se dočetl, že je to kvůli tomu, že `ld` odmítá programy, které by při oné alokaci paměti, o které jsem psal výše, alokovaly víc než 2 GB paměti.
Dal jsem se do počítání a zjistil jsem, že můj program by alokoval ~390 GB paměti, kdyby zaplnil všechno.
Proto potřebuju nějak vypnout nebo obejít tenhle proces, při kterém se alokuje paměť.

Jde to nebo je to nezbytné pro procesy, které `ld` provádí?
Díky


P.S. Opravdu potřebuju alokovat takové množství paměti.

Původní titulek: `ld` alokuje příliš mnoho paměti nebo se ukončí
« Poslední změna: 13 Duben 2011, 13:40:26 od Royal »

MacHala

  • Závislák
  • ****
  • Příspěvků: 1104
  • Big Bro iz watching joo!
    • Zobrazit profil
    • ZlejT
Re: `ld` alokuje příliš mnoho paměti nebo se ukončí
« Odpověď #1 kdy: 13 Duben 2011, 02:13:25 »
muzes to zkusit vysvetlit jeste jednou pochopitelneji (a idelane prihodit nejaky ukazkovy zdrojak?)

jinak male info:
kdyz budes mit globalni "int pole[10000000];", tak se to projevi na velikosti binarky (linker si to pri sestavovani urcite alokuje, otazkou je kolikrat)
kdyz budes mit lokalni "int pole[10000000];", tak to dost mozna neunese stack

v obou pripadech bude mnohem lepsi pouzit malloc
Prislusnik ligy, za kreativni pouzivani interpunkcnich znamenek, carek, predevsim.
=======================================
Tweetuju jako http://twitter.com/zl8

Royal

  • Návštěvník
  • *
  • Příspěvků: 31
    • Zobrazit profil
Re: `ld` alokuje příliš mnoho paměti nebo se ukončí
« Odpověď #2 kdy: 13 Duben 2011, 13:39:40 »
Mám globální "int pole[315101][315101];", jehož alokaci bych potřeboval vyřešit nějak elegantněji.

Potřebuji, aby to pole bylo globální a zároveň aby se skutečně alokovala jen ta část, kterou využívám (v poli budou zapsané 2/315101 - tedy 630202 čísel - a program bude vždy číst jen ze souřadnic, do kterých bylo předtím zapsáno).

MacHala

  • Závislák
  • ****
  • Příspěvků: 1104
  • Big Bro iz watching joo!
    • Zobrazit profil
    • ZlejT
Re: Alokace velkého globálního pole
« Odpověď #3 kdy: 13 Duben 2011, 17:37:29 »
v tom pripade k tomu pouzij nejakou jinou datovou strukturu, protoze alokovat misto 2n pameti n^2 je desna blbost... mozna hash tabulka s indexy jako klicem?

doporucuji nastudovat aspon zaklady algoritimizace a s tim spojenych datovych struktur...
Prislusnik ligy, za kreativni pouzivani interpunkcnich znamenek, carek, predevsim.
=======================================
Tweetuju jako http://twitter.com/zl8

Royal

  • Návštěvník
  • *
  • Příspěvků: 31
    • Zobrazit profil
Re: Alokace velkého globálního pole
« Odpověď #4 kdy: 13 Duben 2011, 17:40:31 »
Pokoušel jsem se nastudovat něco takového, kde může být klíč char [] nebo char *.

Mohl bys mi, prosím, poradit, co mám použít?

Kedrigern

Re: Alokace velkého globálního pole
« Odpověď #5 kdy: 13 Duben 2011, 17:55:26 »
Pokoušel jsem se nastudovat něco takového, kde může být klíč char [] nebo char *.

Mohl bys mi, prosím, poradit, co mám použít?

No pokud používáš C++ tak máš vše připravené (myslím, že si nepsal,že si omezen na ANSI C, nebo ano?).
Kód: [Vybrat]
#include <map>

int main() {
 std::map<char, char> m;
 m['c'] = 'd';
}
Samozřejmě vše lze nastudovat zde:
http://www.cplusplus.com/reference/stl/map/

Pokud nemáš s c++ problém, tak ti poradím i více. Pokud chceš jen c, tak to bude složitější (není v něm tak rozsáhla standartní knihovna).

Royal

  • Návštěvník
  • *
  • Příspěvků: 31
    • Zobrazit profil
Re: Alokace velkého globálního pole
« Odpověď #6 kdy: 13 Duben 2011, 17:59:02 »
Ještě jsem v C++ nikdy nepsal, ale velký problém s ním nemám.

Napíšu to v C++, aspoň se naučím další jazyk.
Díky.

A pro zajímavost/naučení se něco nového: Jak se tohle implementuje v C?

MacHala

  • Závislák
  • ****
  • Příspěvků: 1104
  • Big Bro iz watching joo!
    • Zobrazit profil
    • ZlejT
Re: Alokace velkého globálního pole
« Odpověď #7 kdy: 13 Duben 2011, 18:03:05 »
celkove mi pripada, ze klades spatne otazky...
doporucuji zacit spis tim, ze popises
o co se celkove pokousis?
proc to delas zrovna v C/C++(tj, jazyku, kteremu ocividne dostatecne nerozumis a ktery je na reseni vetsiny beznych problemu zbytecne nizkourovnovy)?

hash tabulka s retezcem jako klicem v C (jeden muj stary domaci ukol):
http://openpaste.org/en/26692/ (pocita to vyskyty jednotlivych slov v souboru)
Prislusnik ligy, za kreativni pouzivani interpunkcnich znamenek, carek, predevsim.
=======================================
Tweetuju jako http://twitter.com/zl8

Royal

  • Návštěvník
  • *
  • Příspěvků: 31
    • Zobrazit profil
Re: Alokace velkého globálního pole
« Odpověď #8 kdy: 13 Duben 2011, 18:21:13 »
Mám zadaných 315100 vrcholů, mezi nimiž je 315100 cest.
Chtěl jsem uložit do pole délky těchto cest tak, aby se k hodnotám dalo rychle přistupovat, a sice "délky[start][cíl] = délka", protože předchozí způsob, kdy jsem měl jen pole cest, byl strašně pomalý; program nestihl doběhnout do hodiny.

Nechtěl jsem vám popsat, o co se přesně pokouším, protože bych to potom měl příliš lehké.
Ale do toho:
Potřebuji mít co nejmenší pole, do kterého se dá narvat 630200 hodnot tak, aby se k hodnotě dalo přistoupit velice rychle, nejlépe tak, jak by to řešil předchozí způsob, kdyby to linker neodmítl zpracovat a kdybych měl víc paměti.

Řešil jsem to v C, protože ostatní jazyky jsou pomalejší než C.

hash tabulka s retezcem jako klicem v C
Díky, možná to použiju.

Kedrigern

Re: Alokace velkého globálního pole
« Odpověď #9 kdy: 13 Duben 2011, 18:32:30 »
Ještě jsem v C++ nikdy nepsal, ale velký problém s ním nemám.

Napíšu to v C++, aspoň se naučím další jazyk.
Díky.

A pro zajímavost/naučení se něco nového: Jak se tohle implementuje v C?
No k C++ nejsou moc dobré učebnice, ale základy se lze naučit... Zkusím ti rychle popsat, co budeš potřebovat.

No v C se to implementuje tak jak je to popsané algoritmicky (to co se o dané struktuře dočteš v návodu/učebnici). Používají se k tomu funkce pro dynamickou alokaci paměti etc. Určitě existuje knihovna, ale ta není součást standartu (čili její přenositelnost může být problém).

V C++ oproti tomu máš sadu datových struktur a algoritmů (popisuje je: cplusplus.com), které jsou definovány v normě a každý správný překladač je má umět. Čili tato knihovna je součástí jazyka. Využivá takzvaný jmenný prostor (namespace) std, který identifikuje vše co patří do této knihovny. V této knihovně jsou:
  • nafukovací pole (pole se zvětšuje dle potřeby):
Kód: [Vybrat]
#include <vector>
...
std::vector<int> pole;
pole.push_back(4);
int i = pole[0]; // i obsahuje 4

  • množiny (normální množina, souhrn prvků, každý prvek je jen jednou):
Kód: [Vybrat]
#include <set>
...
std::set<int> mn;
mn.insert(3);
mn.insert(4);
mn.insert(3);
// mn obsahuje prvky 3,4
  • asociativní mapy, tedy struktura kam ukládáš dvojici klíč a hodnota. Klíč i hodnota mohou být libovolný typ. Jak jsem ukázal v minulém příspěvku.
  • V nové normě (g++ to již podporuje) jsou i struktury, které jsou hashované
  • mnohé další


Nicméně MacHala se ptá dobře. Pokud se chceš naučit programovat jen tak ze zájmu, tak doporučuji nejdřív Python (obecně, python 3). Až budeš mít nějaké zkušenosti, tak si pořídit dobrou učebnici (D.E.Knuth: Umění programování; P.Topfer: Algoritmy a programovací techniky ) a zkus jí pochopit.

Samozřejmě je možné, že máš třeba ve škole něco nařízeno. Ale stejně bych ti doporučil nepouštět se nějak hluboko do Pascalu, C, C++ etc. A použít něco jednodušího, co ti pomůže uchopit koncepty. A v těch nízkoúrovňových jazycích udělat jen to, co musíš.

Royal

  • Návštěvník
  • *
  • Příspěvků: 31
    • Zobrazit profil
Re: Alokace velkého globálního pole
« Odpověď #10 kdy: 13 Duben 2011, 19:09:22 »
Jsi už třetí člověk, který mi onu knížku od P. Topfera doporučil. Asi se po ní vážně podívám.

Na Python jsem se taky díval, ale je pro mé potřeby moc pomalý. Taky jsem psal v C#, ale taky jsem se setkal s neúspěchem v podobě uvařeného procesoru a žádného výsledku. V PHP jsem taky občas psal řešení úloh, které se dají vyřešit napsáním správného algoritmu, nikoliv optimálního.
Nepsal bych tohle v C, kdybych nemusel.

MacHala

  • Závislák
  • ****
  • Příspěvků: 1104
  • Big Bro iz watching joo!
    • Zobrazit profil
    • ZlejT
Re: Alokace velkého globálního pole
« Odpověď #11 kdy: 13 Duben 2011, 20:18:04 »
jen tak mimochodem:
1 vyber z asociativniho pole o velikosti milion polozek v pythonu3 na mem ntb, co jsem ted zkousel, trval priblizne 0.0001s - opravdu se ti vyplati se s tim psat v C?
Prislusnik ligy, za kreativni pouzivani interpunkcnich znamenek, carek, predevsim.
=======================================
Tweetuju jako http://twitter.com/zl8

Kedrigern

Re: Alokace velkého globálního pole
« Odpověď #12 kdy: 14 Duben 2011, 10:39:38 »
Royal: Nevím jaké máš základy a nechci tě urazit trivialitami. I na mém 2x 3.6Ghz jsem napsal v C algoritmus, který chroustal 10 minut. Jak jsem si několikrát ověřil, tak to nebylo špatným zapsaním, ale složitostí úlohy (problém batohu pro vstup v řádech desítek milionů kusů).

Občas se tomu nevyhneš. Na druhou stranu jsou věci, které vypadají zcela stejně a dlouho se tak běžně psaly, ale někdo přišel na nějakou věc, která je strašlivě urychlí (dynamické programování).

Při dnešních výkonech režie jazyků zmizí. Byl jsem nedávno donucen napsat efektivní kompresní program v C#... docela mazec. Bylo k tomu třeba vědět fakt děsně detaiů o tom jazyku. Ale šlo to a nebylo to pomalé.

Opravdu je to o znalostech a zkušenostech. Já jsem k Topferovi chodil na přednášky v úvodním kurzu na VŠ. Kniha je to příjemně udělaná, není přespříliš odborná (nadužívání odborných termínů), ale zároveň je v ní toho hodně. V poměru cena / kolik se z ní naučíš / čas / rychlost hledání je opravdu dobrá. Dodnes jí sem tam vytáhnu, když si chci ověřit, že něco je tak jak si myslím.

Jen je psaná pro pascal. Ale ono to nevadí. Freepascal je víceméně ekvivalent C s pascalovskou syntaxí (když jsem v něm psal třeba pole v dokumentaci nebyly s odkazem na to, že jsou stejná jako v C). Je v něm psán třeba HedgeWars či FrozenBubble. Čili není třeba se bát výkonu.
« Poslední změna: 14 Duben 2011, 10:41:42 od Kedrigern »