/ Forside / Teknologi / Udvikling / C/C++ / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
C/C++
#NavnPoint
BertelBra.. 2425
pmbruun 695
Master_of.. 501
jdjespers.. 500
kyllekylle 500
Bech_bb 500
scootergr.. 300
gibson 300
molokyle 287
10  strarup 270
Hjælp mig af med en macro!
Fra : Per Abrahamsen


Dato : 02-05-03 13:05

Hej.

Jeg har en masse linier i stil med

log.output ("foo", a + b);

der tillader brugeren at "logge" state i en simulation jeg kører.

Min profilering viser vare at hvis folk vil logge mange ting bliver
systemet domineret af strcmp. Så i stedet for "foo" vil jeg gerne
kunne bruge en int. En løsning kan være

static const int foo_id = name2id ("foo");
log.output (foo_id, a + b);

hvor name2id er en funktion der tildeler hver unik streng et unikt
nummer. Men jeg harikke lyst til at hav en ekstra linie for hver ting
der kan logges, så i stedet har jeg lavet en makro

#define output_value(log, key, value)\
do { \
static const int MACRO_id = name2id (key); \
(log).output (MACRO_id, (value)); \
} while (false)

output_value (log, "foo", a + b);

Det giver en anseelig speedup, men jeg ville gerne slipper for at
bruge makroer, så jeg leder efter ideer til et alternativ.

En template ville være ideel

template<const char *const name>
void output_value (Log& log, double value)
{
static const int id = name2id (name);
log.output (id, value);
}

output_value<"log"> (log, a + b);

men C++ tillader ikke "literal strings" som template argumnter.

Den traditionelle enum

enum id_type { LOG_ID, FOO_ID, BAR_ID ... };

er helt udelukket, den sparer ikke plads og der er nogle eneklete
"ids" der først kendes på run-time, og viden om identifier (log
variable) er distribueret i programmet så en sådan central enum ville
være uønsket.

Er der en bedre løsning en makroen?

 
 
Soeren Sandmann (02-05-2003)
Kommentar
Fra : Soeren Sandmann


Dato : 02-05-03 13:43

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Min profilering viser vare at hvis folk vil logge mange ting bliver
> systemet domineret af strcmp. Så i stedet for "foo" vil jeg gerne
> kunne bruge en int. En løsning kan være

Det er ikke rigtig et svar på spørgsmålet, men har du prøvet at bruge
din egen version af strcmp():

int
my_strcmp (const char *s1, const char *s2)
{
if (s1 == s2)
return 0;
else
return strcmp (s1, s2);
}

Hvis log-navnene generelt er konstante, så vil strcmp() ofte blive
kaldt med to identiske pointere. Desuden vil oversættere generelt slå
identiske strengkonstanter sammen, så "foo" og "foo" vil resultere i
den samme pointer.

Jeg ved ikke med andre libc'er, men strcmp() i GNU libc har ikke den
optimering indbygget.

Per Abrahamsen (03-05-2003)
Kommentar
Fra : Per Abrahamsen


Dato : 03-05-03 15:07

Soeren Sandmann <sandmann@daimi.au.dk> writes:

> Hvis log-navnene generelt er konstante, så vil strcmp() ofte blive
> kaldt med to identiske pointere. Desuden vil oversættere generelt slå
> identiske strengkonstanter sammen, så "foo" og "foo" vil resultere i
> den samme pointer.

Desværre er det kun det ene argument til strcmp der er en manifest
konstant, det andet argument er en streng der læses fra en fil når
programmet initialiseres. Så de to argumenter vil aldrig pege på
samme adresse.

....

Til gengæld er det gået op for mig hvorfor Lisp både har en symbol
type og en string type.

Mogens Hansen (03-05-2003)
Kommentar
Fra : Mogens Hansen


Dato : 03-05-03 19:28


"Per Abrahamsen" <abraham@dina.kvl.dk> wrote

[8<8<8<]
> Jeg har en masse linier i stil med
>
> log.output ("foo", a + b);
>
> der tillader brugeren at "logge" state i en simulation jeg kører.
>
> Min profilering viser vare at hvis folk vil logge mange ting bliver
> systemet domineret af strcmp. Så i stedet for "foo" vil jeg gerne
> kunne bruge en int.

Jeg går ud fra at der til "foo" er associeret en eller anden form for
information, og det er derfor at der laves en masse "strcmp".

Kunne det være en idé at bruge en hashing fuktion inde i kaldet til
"log.output", så den associerede information kan findes hurtigere ?
Eventuelt kunne man bruge en klasse som "hash_map" fra STLPort til at knytte
tekststrengen og den associerede information sammen.

> En løsning kan være
>
> static const int foo_id = name2id ("foo");
> log.output (foo_id, a + b);
>
> hvor name2id er en funktion der tildeler hver unik streng et unikt
> nummer. Men jeg harikke lyst til at hav en ekstra linie for hver ting
> der kan logges, så i stedet har jeg lavet en makro
>
> #define output_value(log, key, value)\
> do { \
> static const int MACRO_id = name2id (key); \
> (log).output (MACRO_id, (value)); \
> } while (false)
>
> output_value (log, "foo", a + b);
>
> Det giver en anseelig speedup, men jeg ville gerne slipper for at
> bruge makroer, så jeg leder efter ideer til et alternativ.

Den vil også kun virke hvis det er samme tekst, der bruges hver gang på et
givent sted - det ved jeg selvfølgelig ikke om det er en rimelig
begrænsning.

>
> En template ville være ideel
>
> template<const char *const name>
> void output_value (Log& log, double value)
> {
> static const int id = name2id (name);
> log.output (id, value);
> }
>
> output_value<"log"> (log, a + b);
>
> men C++ tillader ikke "literal strings" som template argumnter.

Nej.
Er der nogen grund til at det skal være en string literal ?
Kunne man tillade sig at skrive noget i retningen af:

class foo
{
public:
// maybe:
static const char* text = "foo text";
};

class bar
{
public:
// maybe
static const char* text = "bar text";
}

log.output<foo>(a+b);
log.output<bar>(c+d);

?


[8<8<8<]
> nogle eneklete
> "ids" der først kendes på run-time, og viden om identifier (log
> variable)

Ok, det udelukker vel nogenlunde brugen af typer som foreslået ovenfor.

[8<8<8<]
> Er der en bedre løsning en makroen?

Forhåbentlig

Venlig hilsen

Mogens Hansen



Per Abrahamsen (04-05-2003)
Kommentar
Fra : Per Abrahamsen


Dato : 04-05-03 12:09

"Mogens Hansen" <mogens_h@dk-online.dk> writes:

> "Per Abrahamsen" <abraham@dina.kvl.dk> wrote
>
> [8<8<8<]
>> Jeg har en masse linier i stil med
>>
>> log.output ("foo", a + b);
>>
>> der tillader brugeren at "logge" state i en simulation jeg kører.
>>
>> Min profilering viser vare at hvis folk vil logge mange ting bliver
>> systemet domineret af strcmp. Så i stedet for "foo" vil jeg gerne
>> kunne bruge en int.
>
> Jeg går ud fra at der til "foo" er associeret en eller anden form for
> information, og det er derfor at der laves en masse "strcmp".

Der bliver lavet en masse strcmp fordi linien ovenfor bliver kaldt en
masse gange (det er en simulering, ovenstående bliver kaldt for hver
time i simuleringen, de længste simuleringer vi har kørt har været et
par tusinde år. Det bliver til en del kald.

Informationer der er knyttet til "foo" i eksemplet er "a + b" og ikke
mere. Det kan dog være "a + b" i flere objekter, der i givet fald vil
blive lagt sammen. Objekter i simuleringen er dynamiske, men
langlivede. Nogen overlever hele simuleringen, andre nogle få
måneder.

> Kunne det være en idé at bruge en hashing fuktion inde i kaldet til
> "log.output", så den associerede information kan findes hurtigere ?
> Eventuelt kunne man bruge en klasse som "hash_map" fra STLPort til at knytte
> tekststrengen og den associerede information sammen.

Det er svært fordi informationen er dynamisk. Men ja, det er i den
retning det burde implementeres for for alvor at vinde hastighed.

>> static const int foo_id = name2id ("foo");

Jeg har label en symbol klasse så jeg kan skrive

static const symbol foo_sym ("foo");

i stedet for. Lidt pænere.

> Den vil også kun virke hvis det er samme tekst, der bruges hver gang på et
> givent sted - det ved jeg selvfølgelig ikke om det er en rimelig
> begrænsning.

Det er netop det faktum at der er samme tekst hver gang jeg kan bruge
til at speede processen op.

> Er der nogen grund til at det skal være en string literal ?

Bekvemmelighed.

> Kunne man tillade sig at skrive noget i retningen af:
>
> class foo
> {
> public:
> // maybe:
> static const char* text = "foo text";
> };
>
> class bar
> {
> public:
> // maybe
> static const char* text = "bar text";
> }
>
> log.output<foo>(a+b);
> log.output<bar>(c+d);
>
> ?

Ja, men så ryger fidusen med at bruge en template eller makro. Ideen
var at spare en linie for hvert kald, men ovenstående får vi alligevel
to linier per kald.

> [8<8<8<]
>> nogle eneklete
>> "ids" der først kendes på run-time, og viden om identifier (log
>> variable)
>
> Ok, det udelukker vel nogenlunde brugen af typer som foreslået ovenfor.

Ikke helt, det betyder bare at man ikke kan bruge samme syntaks for
de tilfælde.

Mogens Hansen (04-05-2003)
Kommentar
Fra : Mogens Hansen


Dato : 04-05-03 21:48


"Per Abrahamsen" <abraham@dina.kvl.dk> wrote

[8<8<8<]
> Der bliver lavet en masse strcmp fordi linien ovenfor bliver kaldt en
> masse gange

Inde i kaldet til "log.output" må der ske mere end f.eks. bare at sende
teksten og værdien ned i en fil - eller var der ikke nogen grund til at
kalde "strcmp".

Jeg forestiller mig at "foo" er navnet på et individ og "a+b" er en egenskab
ved individet på det pågældende tidspunkt - f.eks. dets vægt.
Man vil så der gemme vægten som funktion af tiden for alle individer. Derfor
skal man finde det rigtige sted at gemme vægten, når "log.output" kaldes.

Altså noget i retningen af (ikke oversat kode):
class logger
{
public:
void output(const string& individual_id_arg, unsigned weigth_arg)
{ individual_weight[individual_id_arg].push_back(weigth_arg); }

private:
map<string, vector<unsigned> > individual_weight;
};

og det vil give en hel masse kald til "strcmp".

Ved at skifte
map<string, vector<unsigned> >
ud med
hash_map<string, vector<unsigned> >
ville jeg forvente en væsentlig performance forbedring.

[8<8<8<]
> Det er netop det faktum at der er samme tekst hver gang jeg kan bruge
> til at speede processen op.

Hvis hvert individ er identificeret ved een tekst - altså een pointer
værdi - kan du bruge den information til at speede programmet op.

Altså noget i retningen af (ikke oversat kode):
class logger
{
public:
void output(const char* individual_id_arg, unsigned weight_arg)
{ individual_weight[individual_id_arg].push_back(weigth_arg); }

private:
map<const char*, vector<unsigned> > individual_weight;
};

Venlig hilsen

Mogens Hansen



Per Abrahamsen (05-05-2003)
Kommentar
Fra : Per Abrahamsen


Dato : 05-05-03 13:29

"Mogens Hansen" <mogens_h@dk-online.dk> writes:

> Ved at skifte
> map<string, vector<unsigned> >
> ud med
> hash_map<string, vector<unsigned> >
> ville jeg forvente en væsentlig performance forbedring.

Det ville det sikkert hvis koden havde set sådan ud

Det er snarere en vector<Column> columns, hvor hver Column får tilbudt
informationen. Om de er interesseret afhænger både af navnet og af
deres state. De kan f.eks. være interesseret i vægt af personer, men
ikke af vægt af møbler, og det kan være de kun er interesseret i en
bestemt persons vægt. Og det kan være morgenvægt, mandagsvægt,
timevægt, eller vægt lige før dates.

Men en map<symbol, set<Column>/**/> bør kunne give ret meget, det er
i sidste ende altid en bestemt attribut der skal logges.

Per Abrahamsen (05-05-2003)
Kommentar
Fra : Per Abrahamsen


Dato : 05-05-03 19:49

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Men en map<symbol, set<Column>/**/> bør kunne give ret meget, det er
> i sidste ende altid en bestemt attribut der skal logges.

Det gav lidt, men ikke signifikant meget. Måske fordi de andre
ændringer allerede havde gjort den del af koden "hurtig nok".

Men det er altid rart at skifte en O(n) algoritme ud med en O(log n).

Per Abrahamsen (11-05-2003)
Kommentar
Fra : Per Abrahamsen


Dato : 11-05-03 15:24

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Per Abrahamsen <abraham@dina.kvl.dk> writes:
>
>> Men en map<symbol, set<Column>/**/> bør kunne give ret meget, det er
>> i sidste ende altid en bestemt attribut der skal logges.
>
> Det gav lidt, men ikke signifikant meget. Måske fordi de andre
> ændringer allerede havde gjort den del af koden "hurtig nok".
>
> Men det er altid rart at skifte en O(n) algoritme ud med en O(log n).

Men det røg igen.

Generelt gik problemet ud på at gennemløbe en træstruktur hvor en
række forskellige log objekter har interesse i forskellige dele af
træstrukturen. Træstrukturen er dynamisk, og log objekternes
"interesseområder" er også dynamiske.

Første optimering gik ud på at erstatte den måde knuderne i træet
identificerer sig på overfor log objekterne fra string til symbol (som
er en kontroleret int). Det gav en fordobling af hastigheden,

Anden optimering gik ud på at flytte koden for
"interessetilkendegivelse" ud fra virtuelle funktioner i de enkelte
log modeller, og ind i inline funktioner i stamklassen. Det gav
yderligere 2 til 3 gange speedup.

Tredje optimering gik ud på at skære antallet af relevante log
objekter ned dynamisk mens jeg gennemløber træstrukturen. Det vil
sige hver gang jeg åbner en indre knude, skupper jeg et lag på

stack<vector<Select*>/**/> active_stack

det gav yderligere en fordobling, og overflødiggjorde de inline
funktioner der blev lavet i anden optimering.

Jeg tror jeg kan få en smule mere ud af det ved at kombinere det med
en dynamisk udgave af Mogens forslag

stack<map<symbol, vector<Select*>/**/>/**/> active_leafs;
stack<map<symbol, vector<Select*>/**/>/**/> active_interiors;

Jeg har da allerede fået tilbagemedling fra en bruger om at tiden for
hans simuleringer er faldet fra 45 minuter til 7.

Men jeg slap aldrig af med makroen.

Per Abrahamsen (11-05-2003)
Kommentar
Fra : Per Abrahamsen


Dato : 11-05-03 22:21

Per Abrahamsen <abraham@dina.kvl.dk> writes:

> Jeg tror jeg kan få en smule mere ud af det ved at kombinere det med
> en dynamisk udgave af Mogens forslag
>
> stack<map<symbol, vector<Select*>/**/>/**/> active_leafs;
> stack<map<symbol, vector<Select*>/**/>/**/> active_interiors;

Det gjorde den langsommere, vi er åbentbart ude hvor opbygningen af
datastrukturerne koster mere end de sparer.

Søg
Reklame
Statistik
Spørgsmål : 177558
Tips : 31968
Nyheder : 719565
Indlæg : 6408924
Brugere : 218888

Månedens bedste
Årets bedste
Sidste års bedste