ld-tigcc - Flash OS BSS Special - Page 4

un symbole qui contient le timestamp unix de l'appel a gcc?

une date+heure+truc par exemple ?

le nb de secondes depuis le 1er janvier 1970 en général (et oui, ça foutra la merde sur tous les systèmes 32 bits en 2038 ^^)

AMHA, ce n'est pas très pratique de devoir écrire "zs" à chaque fois qu'on veut faire un calcul. Le calcul formel est mieux intégré dans AMS.

C'est clair, PpHd tu ne fais aucun effort vraiment, on dirait que tu fous rien...

franchement, ça craint, c'est clair ()

Kevin Kofler (./95) :
AMHA, ce n'est pas très pratique de devoir écrire "zs" à chaque fois qu'on veut faire un calcul. Le calcul formel est mieux intégré dans AMS.

La prochaine tu liras tout ou tu te coucheras avant si tu es fatigué, avant d'écrire.

Sasume (./96) :
C'est clair, PpHd tu ne fais aucun effort vraiment, on dirait que tu fous rien...

Hé, ce n'est pas ça que je voulais dire!

./94: c'est cela, si ce n'est que TI a choisi une date de départ différente, à savoir le 1er janvier 1997, 00h00 dans un certain fuseau horaire

J'ai écrit "timestamp de compilation", mais en réalité, c'est plus probablement le timestamp de la signature cryptographique par TI (parce que les FlashApps ont également un timestamp).
Sur AMS 2.05 89, le cert field du timestamp (0x326 0x904 0xnnnnnnnn) est stocké à ROM_BASE+0x12033-0x1203A, et le timestamp vaut 0x0699b9e2, c'est à dire qu'il représente le 07/05/2000 (mm/jj/yyyy) 16h31m30s (dans un certain fuseau horaire).
Le timestamp d'OurWorld 1.0 est 0x0df33de3.

(Rassurez-vous, je ne calcule pas tout ça à la main: quand ils sont appelés avec les bons paramètres, ROM_CALL_504 et ROM_CALL_58E font le boulot à ma place. J'ai documenté au moins le deuxième.)

Au passage, ./99: on le sait à peu près tous que tu n'as pas voulu signifier cela

A la limite, sans la deuxième phrase, la remarque ./95 n'aurait été que redondante: cf. ma remarque, sur un mode plus humoristique, en ./81 et la réponse de PpHd en ./82.
Mais avec la deuxième phrase, le post devient pas constructif: c'est irréaliste d'attendre de PedroM une aussi bonne intégration du CAS que dans AMS, alors que l'introduction du CAS dans PedroM est très récente.
D'où les réactions. Pas plus compliqué que cela.

Build de PedroM avec la suite de tests de MPFR:

Program Statistics:
  Program Variable Name:                    main\pedrom
  Program Variable Size:                    944205 Bytes
  BSS Size:                                 12358 Bytes
  Absolute Relocs:                          0
  Natively Emitted Relocs:                  0
  Relocs Removed by Branch Optimization:    1688
  Relocs Removed by Move Optimization:      2236
  Relocs Removed by Test Optimization:      12
  Relocs Removed by Calc Optimization:      13
  Relocs Removable by F-Line Jumps:         86169
  Space Saved by Range-Cutting:             8016 Bytes

Temps pris par ld-tigcc : 10 MINUTES !

Ton Flash OS a presque la taille de AMS là, il ne faut pas t'attendre à ce que ld-tigcc le linke rapidement. Surtout si tu y mets une test suite qui doit avoir je ne sais pas combien de fichiers objet (probablement beaucoup plus que AMS, même si je ne peux pas le dire exactement parce que les sources de AMS ne sont pas disponibles). (Pour moi, une test suite est quelque chose qu'on rm -rf immédiatement parce que ça met trop longtemps à compiler. C'est ce que je fais avec celles dans GCC et Binutils en tout cas. ) N'oublie pas que ld-tigcc est conçu primairement pour les programmes de <= 64 KO.

c'est clair

sinon c'est un bon stress test pour ld-tigcc

Kevin Kofler (./104) :
C'est ce que je fais avec celles dans GCC et Binutils en tout cas

C'est surtout que dans le cadre de tigcc, et d'une cross compilation, ca n'est jamais simple de lancer les tests...

Kevin Kofler (./104) :
Ton Flash OS a presque la taille de AMS là, il ne faut pas t'attendre à ce que ld-tigcc le linke rapidement.

Parce que tu crois que le linkeur GNU ld, met 10 minutes pour linker un programme de 10 Mo.

Kevin Kofler (./104) :
Pour moi, une test suite est quelque chose qu'on rm -rf immédiatement parce que ça met trop longtemps à compiler.

C'est essentiellement utile pour les développeurs.

Parce que tu crois que le linkeur GNU line, met 10 minutes pour linker un programme de 10 Mo.

Pas faux, ça...

Un des meilleurs profileurs est callgrind - mais là, 10 minutes en natif, c'est un peu trop long pour qu'il soit facile de faire exécuter le linking à callgrind avec simulation des caches et du HW prefetch. Ca ralentit de plus de deux ordres de grandeur sur ma machine...

Bah, il n'y a pas grand chose à profiler, la seule structure de données dans ld-tigcc (à part à un endroit du réordonnement de sections qui n'est pas activé ici, où des tableaux sont utilisés) est la liste chaînée. La table de hachage est un concept totalement inconnu de ld-tigcc. Bref, ce n'est pas la peine de chercher longtemps pourquoi ça prend tout ce temps.

Voilà le code qui va chercher un symbole par son nom:

// Point the location to the appropriate symbol, if one is found.
SYMBOL *ResolveLocation (PROGRAM *Program, SECTION *Section, LOCATION *Location)
{
	if (Location->Symbol)
		return Location->Symbol;
	else
	{
		SECTION *CurSection;
		
		// For each section...
		for_each (CurSection, Program->Sections)
		{
			SYMBOL *CurSymbol;
			
			// For each symbol...
			for_each (CurSymbol, CurSection->Symbols)
			{
				// If the name matches, we have found the right symbol.
				if (CurSymbol->Exported && (!(strcmp (Location->SymbolName, CurSymbol->Name))))
				{
					// Set up the reloc accordingly, freeing its
					// destination string.
					Location->Symbol = CurSymbol;
					FreeLocationSymbolName (Section, Location);
					return CurSymbol;
				}
			}
		}
		
		return NULL;
	}
}

(et la macro for_each fait exactement ce que vous craignez ).

Petit profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 45.35    205.93   205.93   366848     0.00     0.00  FindRelocAtPos
 44.98    410.19   204.26   351120     0.00     0.00  FindSymbolAtPos
  4.18    429.19    19.00     3979     0.00     0.01  CutRange
  4.01    447.40    18.21    21057     0.00     0.00  ResolveLocation
  0.62    450.23     2.83   432366     0.00     0.00  FindSegmentAtPos
  0.56    452.79     2.56     1432     0.00     0.24  MergeSections
  0.15    453.49     0.70 52765585     0.00     0.00  AdjustLocationForRangeCut
  0.04    453.66     0.17    28669     0.00     0.00  DisableRangeCutting
  0.02    453.75     0.09   388974     0.00     0.00  M68kFixReloc
  0.02    453.82     0.07      394     0.00     0.88  M68kFixCodePreMerge
  0.01    453.86     0.04   374531     0.00     0.00  FindSegment
  0.01    453.89     0.03   458178     0.00     0.00  GetLocationOffset
  0.01    453.92     0.03   305108     0.00     0.00  IsBinaryDataRange
  0.00    453.94     0.02   308893     0.00     0.00  FindLibCallAtPos
  0.00    453.96     0.02   308893     0.00     0.00  FindROMCallAtPos
  0.00    453.98     0.02        3     0.01     2.82  ImportAmigaOSFile
  0.00    453.99     0.01   308893     0.00     0.00  FindRAMCallAtPos
  0.00    454.00     0.01   227304     0.00     0.00  ReadTI4
  0.00    454.01     0.01   117537     0.00     0.00  ResolveReloc
  0.00    454.02     0.01    78949     0.00     0.00  FreeLocationSymbolName
  0.00    454.03     0.01    57837     0.00     0.00  InsertReloc
  0.00    454.04     0.01    29167     0.00     0.00  GetCalcBuiltinLocationValue
  0.00    454.05     0.01    28668     0.00     0.00  FixupRelativeReloc
  0.00    454.06     0.01      374     0.00     0.00  ImportSymbolFromArchive
  0.00    454.07     0.01        1     0.01     0.21  ExportFlashOSFile
  0.00    454.07     0.00   423488     0.00     0.00  IsCodeRange
  0.00    454.07     0.00   187208     0.00     0.00  ReadTI1
  0.00    454.07     0.00   126478     0.00     0.00  ReadTI2
  0.00    454.07     0.00   116147     0.00     0.00  HandleLocation
  0.00    454.07     0.00    86507     0.00     0.00  ReadSTI
  0.00    454.07     0.00    57837     0.00     0.00  FreeReloc
  0.00    454.07     0.00    57837     0.00     0.00  FreeRelocRelation
  0.00    454.07     0.00    57837     0.00     0.00  WriteTI
  0.00    454.07     0.00    57835     0.00     0.00  GetFileName
  0.00    454.07     0.00    57809     0.00     0.00  IncRefCounts
  0.00    454.07     0.00    43162     0.00     0.00  HandleSpecialSymbol
  0.00    454.07     0.00    40590     0.00     0.00  InsertSymbol
  0.00    454.07     0.00    33871     0.00     0.00  HandleInsertion
  0.00    454.07     0.00    31325     0.00     0.00  M68kIsRelocOptimizable
  0.00    454.07     0.00    29237     0.00     0.00  GetCalcBuiltinValues
  0.00    454.07     0.00    29167     0.00     0.00  EmitCalcBuiltinValue
  0.00    454.07     0.00    29167     0.00     0.00  GetCalcBuiltinValue
  0.00    454.07     0.00    29141     0.00     0.00  FindMatchingReloc
  0.00    454.07     0.00    28670     0.00     0.00  AddTI
  0.00    454.07     0.00    28670     0.00     0.00  IsZeroDataRange
  0.00    454.07     0.00    28668     0.00     0.00  FindCompatibleReloc

Je crois que ce qu'il faut optimiser est évident

               0.00    0.00       1/305108      M68kRemoveTrailingNOP [56]
                0.00    1.36    1189/305108      M68kFixCodePreMerge [4]
                0.00   30.86   26998/305108      M68kIsRelocOptimizable [15]
                0.03  316.54  276920/305108      M68kFixReloc [6]
[2]     76.8    0.03  348.76  305108         IsBinaryDataRange [2]
              177.49    0.00  305108/351120      FindSymbolAtPos [8]
              171.22    0.00  305014/366848      FindRelocAtPos [7]
                0.02    0.00  304902/308893      FindROMCallAtPos [42]
                0.02    0.00  304902/308893      FindLibCallAtPos [41]
                0.01    0.00  304902/308893      FindRAMCallAtPos [43]
-----------------------------------------------
                0.00  346.51      20/20          main [1]
[3]     76.3    0.00  346.51      20         MergeAllSections [3]
                2.56  335.20    1432/1432        MergeSections [5]
                0.00    8.75      10/12          M68kFixCode [20]
                0.00    0.00       5/1437        HandleSectionContents [26]
-----------------------------------------------
                0.00   10.50      12/394         M68kFixCode [20]
                0.07  334.29     382/394         MergeSections [5]
[4]     75.9    0.07  344.79     394         M68kFixCodePreMerge [4]
                0.09  334.61  388974/388974      M68kFixReloc [6]
                0.00    6.25    1025/3984        M68kCutOrFillRange [16]
                0.00    2.46  423488/423488      IsCodeRange [24]
                0.00    1.36    1189/305108      IsBinaryDataRange [2]
                0.03    0.00  399871/458178      GetLocationOffset [39]
-----------------------------------------------
                2.56  335.20    1432/1432        MergeAllSections [3]
[5]     74.4    2.56  335.20    1432         MergeSections [5]
                0.07  334.29     382/394         M68kFixCodePreMerge [4]
                0.00    0.83    1432/1437        HandleSectionContents [26]
                0.00    0.00    1432/1434        FreeSection [52]
                0.00    0.00       1/28669       DisableRangeCutting [37]
                0.00    0.00    2864/2864        CreateSectionSegment [77]
                0.00    0.00    1431/1431        GetPaddedSize [81]
                0.00    0.00     190/195         FinalizeRangeCutting [86]
-----------------------------------------------
                0.09  334.61  388974/388974      M68kFixCodePreMerge [4]
[6]     73.7    0.09  334.61  388974         M68kFixReloc [6]
                0.03  316.54  276920/305108      IsBinaryDataRange [2]
                0.00   18.03    2959/3984        M68kCutOrFillRange [16]
                0.00    0.00       5/6           CutSection [53]
-----------------------------------------------
                0.00    0.00       6/366848      FindMatchingReloc [54]
                0.00    0.00       6/366848      CanShrinkSection [51]
                0.00    0.00       6/366848      CutSection [53]
                2.23    0.00    3979/366848      CutRange [17]
               32.47    0.00   57837/366848      InsertReloc [13]
              171.22    0.00  305014/366848      IsBinaryDataRange [2]
[7]     45.4  205.93    0.00  366848         FindRelocAtPos [7]
                0.00    0.00       6/351120      CanShrinkSection [51]
                0.84    0.00    1437/351120      HandleSectionContents [26]
                2.31    0.00    3979/351120      CutRange [17]
               23.61    0.00   40590/351120      InsertSymbol [18]
              177.49    0.00  305108/351120      IsBinaryDataRange [2]
[8]     45.0  204.26    0.00  351120         FindSymbolAtPos [8]
-----------------------------------------------
                0.01   94.82  117537/117537      ResolveRelocs [10]
[9]     20.9    0.01   94.82  117537         ResolveReloc [9]
                0.00   65.59     374/375         ImportArchiveObject [12]
               18.21    0.00   21057/21057       ResolveLocation [19]
                0.00   11.00   20612/57809       IncRefCounts [14]
                0.01    0.00     374/374         ImportSymbolFromArchive [49]
                0.00    0.00     445/445         ResolveSpecialSymbolRelocTarget [60]
                0.00    0.00     445/445         TranslateSpecialExternalSymbol [85]
-----------------------------------------------
                0.00   94.83       3/3           main [1]
[10]    20.9    0.00   94.83       3         ResolveRelocs [10]
                0.01   94.82  117537/117537      ResolveReloc [9]
-----------------------------------------------
                0.00    1.75      10/385         main [1]
                0.00   65.77     375/385         ImportArchiveObject [12]
[11]    14.9    0.00   67.52     385         ImportCOFFFile [11]
                0.01   46.37   51256/57837       InsertReloc [13]
                0.00   21.13   36323/40590       InsertSymbol [18]
                0.01    0.00  204310/227304      ReadTI4 [44]
                0.00    0.00     298/29141       FindMatchingReloc [54]
                0.00    0.00  163589/187208      ReadTI1 [64]
                0.00    0.00   95688/126478      ReadTI2 [65]
                0.00    0.00   51256/86507       ReadSTI [67]
                0.00    0.00   41951/43162       HandleSpecialSymbol [69]
                0.00    0.00    2826/2831        CreateSectionSymbol [78]
                0.00    0.00    1413/1416        InsertSection [83]
                0.00    0.00    1413/1416        GetStartupSectionNumber [82]
                0.00    0.00     298/116147      HandleLocation [66]
                0.00    0.00      17/17          MakeCommonSymbol [89]
-----------------------------------------------
                0.00    0.18       1/375         CheckGlobalImport [34]
                0.00   65.59     374/375         ResolveReloc [9]
[12]    14.5    0.00   65.77     375         ImportArchiveObject [12]
                0.00   65.77     375/385         ImportCOFFFile [11]
                0.00    0.00     375/388         ImportObjectFile [62]
-----------------------------------------------
                0.00    5.95    6581/57837       ImportAmigaOSFile [21]
                0.01   46.37   51256/57837       ImportCOFFFile [11]
[13]    11.5    0.01   52.33   57837         InsertReloc [13]
               32.47    0.00   57837/366848      FindRelocAtPos [7]
                0.00   19.86   37197/57809       IncRefCounts [14]
                0.00    0.00  115674/116147      HandleLocation [66]

Bah, le code, il est là:
http://tigcc-linux.cvs.sourceforge.net/tigcc-linux/tigcc/ld-tigcc/manip.c?revision=1.10&view=markup
Challenge: trouvez les fonctions FindRelocAtPos et FindSymbolAtPos. Indice: une recherche ne les trouve pas, et pourtant le code est là-dedans. Autre indice: j'ai déjà plusieurs fois montré le code en question comme exemple sur ce forum. Je vous laisse chercher.

  342 // Find the item preceding or following the given location. May return NULL.
  343 #define DefineFindItemAtPos(Type,Item,LocationSuffix) \
  344 Type *Find##Item##AtPos (const SECTION *Section, OFFSET Location, BOOLEAN Following) \
  345 { \
  346 	/* Find the place so that Item->Location is always less than Location */ \
  347 	/* and Next##Item->Location is always greater or equal. */ \
  348 	Type *Item = NULL, *Next##Item = NULL; \
  349 	if (Location > Section->Size >> 1) \
  350 	{ \
  351 		Item = GetLast (Section->Item##s); \
  352 		while (Item && (Item->Location LocationSuffix >= Location)) \
  353 		{ \
  354 			Next##Item = Item; \
  355 			Item = GetPrev (Item); \
  356 		} \
  357 	} \
  358 	else \
  359 	{ \
  360 		Next##Item = GetFirst (Section->Item##s); \
  361 		while (Next##Item && (Next##Item->Location LocationSuffix < Location)) \
  362 		{ \
  363 			Item = Next##Item; \
  364 			Next##Item = GetNext (Next##Item); \
  365 		} \
  366 	} \
  367 	/* If we are looking for something that follows, the case is clear. */ \
  368 	/* Otherwise, we need to check whether the next item is also OK. */ \
  369 	if (Following || (Next##Item && (Next##Item->Location LocationSuffix <= Location))) \
  370 		return Next##Item; \
  371 	else \
  372 		return Item; \
  373 }
  374 
  375 DefineFindItemAtPos (SYMBOL,   Symbol,  );
  376 DefineFindItemAtPos (RELOC,    Reloc,   );
  377 DefineFindItemAtPos (ROM_CALL, ROMCall, );
  378 DefineFindItemAtPos (RAM_CALL, RAMCall, );
  379 DefineFindItemAtPos (LIB_CALL, LibCall, );
  380 DefineFindItemAtPos (SEGMENT,  Segment, .Start->Location);
  381 
  382 #undef DefineFindItemAtPos

?

edit : ça me rend malade tout ça, pas envie d'en lire plus

Je savais très bien que la seule structure de données de ld-tigcc était la liste chaînée, mais je voulais savoir à quel point c'était un carnage. Maintenant, avec les chiffres de ./112, je sais

Vu que 90% du temps est passé dans les fonctions de liste chaînée, une accélération de 5x ne semble pas irréaliste ^^
Un arbre binaire ordonné qui reste assez équilibré sans être trop coûteux (red-black, par exemple) améliorerait déjà les choses, mais sur des grands volumes de données, ils ne peuvent pas rivaliser avec une hashtable...

beaucoup plus que 5x, c'est plus la même complexité de toutes façons.
Nan mais qu'est ce qu'il y a de compliqué à utiliser une hashmap sans déconner ??? (même à faire c'est pas du tout compliqué, j'en ai fait une dans mon premier programme C, un éditeur/optimiseur de tiles, et pourtant je n'y connaissais vraiment rien )
Après, que le programme ne soit pas lisible c'est autre chose, mais au niveau algo y'a vraiment rien de compliqué quand même, je ne comprend pas (au pire, si y'a des effets de bords partout, il suffit de convertir la liste en hashmap juste pour les fonctions qui posent problème, non ?)

Je donnais 5x comme borne inférieure (= si on n'arrive pas à accélérer le linker d'au moins cette quantité, c'est qu'on ne s'applique pas)
C'est clair qu'avec une hash table de taille bien choisie (=> taux de remplissage pas trop élevé; si on sait dès le début combien de sections il y a, on pourrait même peut-être adapter la taille de la table et la fonction de hash au nombre de sections), on peut faire mieux que ça.

Ximoon (./114)

Voilà notre gagnant! Dommage que tu ne gagnes rien.

Lionel Debroux (./115) :
Un arbre binaire ordonné qui reste assez équilibré sans être trop coûteux (red-black, par exemple) améliorerait déjà les choses, mais sur des grands volumes de données, ils ne peuvent pas rivaliser avec une hashtable...

Les fonctions qui consomment le plus de temps dans le profile de PpHd sont des fonctions qui recherchent des symboles par position, pas par nom, donc l'idée de l'arbre équilibré m'a l'air meilleure.

Kevin Kofler (./118) :
Les fonctions qui consomment le plus de temps dans le profile de PpHd sont des fonctions qui recherchent des symboles par position, pas par nom, donc l'idée de l'arbre équilibré m'a l'air meilleure.

A mon avis aussi.

Quelqu'un s'est amusé à implémenter l'utilisation d'arbres équilibrés à la place de l'utilisation de listes chaînées ?

Je suis en train de faire un miroir Git du repository CVS TIGCC, pour essayer l'import depuis CVS et pour pouvoir bosser avec un vrai SCM quand je reprendrai et finirai les patches pour le support du timestamp de compilation...
C'est affreusement lent, au mieux une révision d'un fichier donné par seconde
Ce n'est pas ma connexion Internet qui limite: j'ai encore fait du téléchargement d'ISO de distros ce matin, en parallèle sur 8 serveurs européens, à plus de 9000 kilo-octets/s pendant des périodes de plusieurs secondes (interrompues parce que mon disque n'est pas capable d'avaler ça)...

[EDIT: yeah, presque deux heures d'import pour 479 révisions...
A la fin, le pack Git comprend 7720 objets et le répertoire .git, quand le pack est généré avec des settings un peu agressifs, consomme moins de 5 MB.]

[EDIT2: j'ai importé également les modules "tigcc-linux" et "ktigcc".
J'ai vu que mon import a rendu le repository nettement plus populaire: le nombre de lectures indiqué à http://sourceforge.net/projects/tigcc-linux/ est passé de moins de 500 à plus de 8500
(et le nombre indiqué de commits est super faux, il y a plus de 750 commits rien que pour le module ktigcc)]