Оптимизация линковки проектов, написанных на С-С++ (1187408)
Текст из файла
Ìèíèñòåðñòâî îáðàçîâàíèÿ è íàóêè Ðîññèéñêîé ÔåäåðàöèèÌÎÑÊÎÂÑÊÈÉ ÔÈÇÈÊÎ-ÒÅÕÍÈ×ÅÑÊÈÉ ÈÍÑÒÈÒÓÒ(ãîñóäàðñòâåííûé óíèâåðñèòåò)ÊÀÔÅÄÐÀ ÈÍÔÎÐÌÀÒÈÊÈÎïòèìèçàöèÿ ëèíêîâêè ïðîåêòîâ, íàïèñàííûõíà C/C++Âûïóñêíàÿ êâàëèôèêàöèîííàÿ ðàáîòà(ìàãèñòåðñêàÿ ðàáîòà)Íàïðàâëåíèå ïîäãîòîâêè: 03.04.01 Ïðèêëàäíàÿ ìàòåìàòèêà è ôèçèêàÂûïîëíèë:ñòóäåíò 6 êóðñà 073 ãðóïïûÒàòóíîâ Êèðèëë Þðüåâè÷Íàó÷íûé ðóêîâîäèòåëü:ê.ô.-ì.í.×óêàíîâà Îëüãà ÂëàäèìèðîâíàÌîñêâà, 2016Ñîäåðæàíèå1 Ââåäåíèå22 Ïîñòàíîâêà çàäà÷è43 Ìîäåëü73.1Îïèñàíèå ìîäåëè . . . . .
. . . . . . . . . . . . . . . . . . .73.2Âûäåëåíèå íåîïòèìàëüíûõ çàâèñèìîñòåé. . . . . . . . . . .94 Ðåàëèçàöèÿ114.1Âûáîð ëèíêåðà. . . . . . . . . . . . . . . . . . . . . . . . .4.2Äîïîëíèòåëüíûå ïðîâåðêè. . . . . . . . . . . . . . . .
. .11135 Îñíîâíûå ðåçóëüòàòû146 Çàêëþ÷åíèå151ÂâåäåíèåÍà÷íåì ñ òîãî, ÷òî îïðåäåëèì, íà ÷òî íàïðàâëåíî äàííîå èññëåäî-âàíèå. Äàííîå èññëåäîâàíèå íàïðàâëåíî â îñíîâíîì íà ïðîåêòû, êîòîðûå ñîáèðàþòñÿ â àâòîìàòè÷åñêîì ðåæèìå íà ðåãóëÿðíîé îñíîâå. Òàêîãîðîäà ïðîåêòû, íàä êîòîðûìè òðóäèòñÿ áîëüøîé êîëëåêòèâ ïðîãðàììèñòîâ, èìåþò òåíäåíöèþ [1] ïåðåñîáèðàòü ïîñëå êàæäîãî êîììèòà â ñèñòåìó êîíòðîëÿ âåðñèé äëÿ ðàííåãî íàõîæäåíèÿ âîçìîæíûõ äåôåêòîâè áàãîâ. Òàêàÿ ïåðåñáîðêà ÿâëÿåòñÿ çàíèìàåò âðåìÿ, êîòîðîå â-ïåðâûõæä¼ò ïðîãðàììèñò äëÿ ïîëó÷åíèÿ ðåçóëüòàòà îò àâòîìàòè÷åñêîé ñèñòåìû ñáîðêè, âî-âòîðûõ ýòî ïðîöåññîðíîå âðåìÿ, áóäü îíî íà ñîáñòâåííîìêëàñòåðå êîìïàíèè, âåäóùåé ðàçðàáîòêè ïðîãðàìíîãî ïðîäóêòà, èëè âîáëàêå, ñòîèò îïðåäåë¼ííûõ äåíåã.Ïðîãðàììèñòû, êîãäà ñîñòàâëÿþò ïðàâèëà äëÿ èñïîëüçóåìîé ñèñòåìûñáîðêè, áóäü òî Make, CMake, qmake èëè ÷òî-òî äðóãîå, íå âñåãäà ñïîñîáíû ïðîñëåäèòü, ÷òî çàâèñèìîñòè, êîòîðûå îíè óêàçûâàþò, äåéñòâèòåëüíîÿâëÿþòñÿ çàâèñèìîñòÿìè ïîñëå êàæäîãî êîììèòà, êîòîðûé îíè äåëàþò.Âîçìîæíî çàâèñèìîñòü òðåáîâàëàñü íåñêîëüêî êîììèòîâ íàçàä, äî òîãî êàê ïðîãðàììèñò óáðàë ñîîòâåòñòâóþùóþ çàâèñèìîñòü èç èñõîäíîãîêîäà, íî íå ïîòðóäèëñÿ óáðàòü å¼ èç ñèñòåìû ñáîðêè.Ïîäîáíîãî ðîäà ïðîáëåìû òðåáóþò êîîðäèíàöèè ñî ñòîðîíû ñèñòåìûñáîðêè (òðåáóåòñÿ îòâåò íà âîïðîñ â äóõå ¾ñ÷èòàåò ëè CMake, ÷òî áèáëèîòåêà A çàâèñèò îò áèáëèîòåêè B?¿), è â îáùåì ñëó÷àå ðàøåíèå áóäåò ñâî¼äëÿ êàæäîé ñèñòåìû ñáîðêè, ïîýòîìó â ýòîì èññëåäîâàíèè ìû ñîñðåäîòî÷èì ñâî¼ âíèìàíèå íà ðåøåíèè, íå çàâèñÿùåì îò êîíêðåòíîé ñèñòåìûñáîðêè. äàííîé ðàáîòå â îñíîâíîì ïîéä¼ò ðå÷ü î óäàëåíèè íåíóæíûõ çà-2âèñèìîñòåé, âîçíèêàþùèõ ïðè ëèíêîâêå îäíîé áèáëèîòåêè ê äðóãîé.
Âïîñëåäóþùèõ ãëàâàõ ìû îïðåäåëèì íåñêîëüêî íåîáõîäèìûõ ïîíÿòèé,îïðåäåëèì èíòåðåñóþùèé íàñ àñïåêò ëèíêîâêè, ðàññìîòðèì, ÷òî òàêîå¾íåîïòèìàëüíàÿ çàâèñèìîñòü¿, ïðåäëîæèì ìîäåëü, íà îñíîâå êîòîðîé íàõîäèòü è ðåøàòü íåîïòèìàëüíûå çàâèñèìîñòè è ðàññìîòðèì ðåçóëüòàòûíà íåêîòîðûõ ïðîåêòàõ ñ îòêðûòûì èñõîäíûì êîäîì.32Ïîñòàíîâêà çàäà÷èÖåëüþ ðàáîòû ÿâëÿåòñÿ ñîêðàùåíèå âðåìåíè ëèíêîâêè îòäåëüíûõ öå-ëåé â ïðîåêòå çà ñ÷åò óäàëåíèÿ íåíóæíûõ çàâèñèìîñòåé.
Íàñ èíòåðåñóåòðåøåíèå, íå çàâèñÿùåå îò êîíêðåòíîé ñèñòåìû ñáîðêè, ïîòîìó ÷òî âîïåðâûõ, òàêîå ðåøåíèå äîëæíî áûòü ñâîèì äëÿ êàæäîé ñèñòåìû ñáîðêè,à âî-âòîðûõ ïîíÿòèå ¾çàâèñèìîñòü¿ ìîæåò áûòü äîâîëüíî ðàñïëûòûì.Íàïðèìåð, â òî âðåìÿ êàê â ñèñòåìå ñáîðêè CMake ñóùåñòâóåò âîçìîæíîñòü óêàçàíèÿ ÿâíûõ çàâèñèìîñòåé ïðè ïîìîùètarget_link_libraries,òàì òàêæå ñóùåñòâóåò âîçìîæíîñòü äîáàâëåíèÿ ñîáñòâåííûõ ïðàâèë èadd_custom_targetêîììàíä ïðè ïîìîùèèadd_custom_command.1Ïî-äîáíûå âîçìîæíîñòè, êîòîðûå ïîçâîëÿþò èäòè â îáõîä òîãî, ÷òî ñèñòåìàñáîðêè ìîãëà áû âûäàòü â êà÷åñòâå çàâèñèìîñòè äëÿ èçó÷åíèÿ, ñóùåñòâåííî óñëîæíÿþò ïîñòðîåíèå ãðàôà çàâèñèìîñòåé.Ïîäîáíîå òðåáîâàíèå âûíóæäàåò èçó÷àòü çàâèñèìîñòè â ïðîåêòå íàóðîâíå ëèíêîâùèêà.
Ñîâðåìåííûå ëèíêîâùèêè, íàïðèìåð ld, îáëàäàþòîáøèðíûì íàáîðîì âñòðîåííûõ âîçìîæíîñòåé.(todo link) Ñðåäè íèõ íàñáóäåò èíòåðåñîâàòü òîëüêî îñíîâíàÿ çàäà÷à ëèíêîâùèêà: ñáîðêà îáúåêòíûõ ôàéëîâ, ãåíåðèðóåìûõ êîìïèëÿòîðîì, è áèáëèîòåê â îäèí ôàéë,ïðåäñòàâëÿþùèé ñîáîé äðóãóþ áèáëèîòåêó, èñïîëíÿåìûé ôàéë èëè åù¼îäèí îáúåêòíûé ôàéë.Òàêèì îáðàçîì, åñëè âî âðåìÿ ëèíêîâêè îáíàðóæèâàåòñÿ, ÷òî èñïîëíÿåìûé ôàéëL,òîEEñîáèðàåòñÿ èç îáúåêòíûõ ôàéëîâçàâèñèò îòo1 , o2è îòLo1 , o2è áèáëèîòåêè(çäåñü è äàëåå îáúåêòíûå ôàéëû îáî-çíà÷àþòñÿ ìàëåíüêèìè áóêâàìè, à áèáëèîòåêè è èñïîëíÿåìûå ôàéëû,1 Íàìîìåíòíàïèñàíèÿíàñàéòågithub.com∼680000ðåçóëüòàòîâïðèïîèñêåtarget_link_libraries è ñóììàðíî ∼300000 ïðè ïîèñêå add_custom_target è add_custom_command,òî åñòü ïðèìåðíî ïîëîâèíà îòtarget_link_libraries.4óæå ïîëó÷åííûå èç ëèíêîâùèêà áîëüøèìè). Îáîçíà÷àòüñÿ ïîäîáíàÿçàâèñèìîñòü áóäåò êàêE → {o1 , o2 , L}.Íåêîòîðûå áèáëèîòåêè ñîáèðàþòñÿ òîëüêî èç îáúåêòíûõ ôàéëîâ.
Âýòîì ñëó÷àå, êîíå÷íî, âåðíî, ÷òîL → {o3 , o4 , o5 },áóäåì îáîçíà÷àòü ïîäîáíóþ êîíñòðóêöèþ êàêíûå ñêîáêè îáîçíà÷àþò, ÷òî áèáëèîòåêàôàéëîâo3 , o4èo5Líî ïîìèìî ýòîãî ìûL = [o3 , o4 , o5 ].Êâàäðàò-áûëà ñîáðàíà èç îáúåêòíûõèëè, èíûìè ñëîâàìè, ðàçáèâàåòñÿ íà ñîîòâåòñòâóþùèåîáúåêòíûå ôàéëû. ïðîåêòàõ ïðîãðàììèñòû íå âñåãäà ñëåäÿò çà îïòèìàëüíîé ðàññòàíîâêîé çàâèñèìîñòåé.
Íàøåé îñíîâíîé öåëüþ â ýòîé ðàáîòå áóäåò ïîèñêíåîïòèìàëüíûõ çàâèñèìîñòåé ñëåäóþùåãî âèäà. Ïóñòüìûé ôàéë èëè áèáëèîòåêà, àAèBE èñïîëíÿå- áèáëèîòåêè. Ðàññìîòðèì òàêóþñèòóàöèþ:E → A → B.Åñëè ñóùåñòâóåò ñïîñîá ðàçáèòü áèáëèîòåêóA2òàêèå, ÷òîA = [A1 , A2 ],èA2Aíå çàâèñèò îòíà äâå áèáëèîòåêèA1 ,A1èòî îïèñàííûé ïðèìåðìîæíî áóäåò ïåðåïèñàòü êàêE → [A1 , A2 ] → B.Èñïîëüçóÿ íåçàâèñèìîñòüA2îòA1ìîæíî èñêëþ÷èòü ëèøíþþ çàâèñè-ìîñòü:E → A1A2 → B.Èñêëþ÷åíèå ïîäîáíûõ çàâèñèìîñòåé ïîçâîëèò ñîêðàòèòü âðåìÿ ñáîðêè îòäåëüíûõ öåëåé â ïðîåêòå, íî ñêîðåå âñåãî íå ñîêðàòèò âðåìÿ ñáîðêèâñåãî ïðîåêòà, ïîòîìó ÷òî íåñìîòðÿ íà òî, ÷òî äëÿ ñáîðêè5Eòåïåðü íåòðåáóåòñÿ ñîáèðàòü è ëèíêîâàòüB,ñîáðàòüBïîòðåáóåòñÿ äëÿ ñáîðêèäðóãîé öåëè ïðîåêòà, êîòîðàÿ äåéñòâèòåëüíî çàâèñèò îò6B.3Ìîäåëü3.1Îïèñàíèå ìîäåëèÂíà÷àëå ìû îïèøåì, êàêîé àñïåêò ëèíêîâêè äëÿ íàñ âàæåí.
Ëèíêîâùèê, êîãäà ñîáèðàåò ôàéëû â äðóãîé ôàéë, çàíèìàåòñÿ ðàçðåøåíèåìñèìâîëîâ. Íàñ èíòåðåñóåò äâà òèïà ñèìâîëîâ: îïðåäåë¼ííûé è íåîïðåäåë¼ííûé. Îïðåäåë¼ííûé ñèìâîë ôóíêöèÿ èëè ïåðåìåííàÿ, îïðåäåë¼ííàÿ â äàííîì ìîäóëå è ïðåäîñòàâëÿåìàÿ äëÿ èñïîëüçîâàíèÿ äðóãèììîäóëÿì, â òî âðåìÿ êàê íåîïðåäåë¼ííûé ñèìâîë ôóíêöèÿ èëè ïåðåìåííàÿ, íà êîòîðûå ññûëàåòñÿ ìîäóëü, íî íå îïðåäåëÿåò èõ âíóòðè ñåáÿ.2Îïðåäåë¼ííûå ñèìâîëû, êàê ïðàâèëî , îïðåäåëåíû òîëüêî â îäíîìôàéëå, â òî âðåìÿ êàê íåîïðåäåë¼ííûå ñèìâîëû ìîãóò èñïîëüçîâàòüñÿâ íåñêîëüèõ ìîäóëÿõ.
Ïðè ýòîì ìîäóëü ñ êàêèì-ëèáî íåîïðåäåë¼ííûìñèìâîëîì áóäåò çàâèñåòü îò ìîäóëÿ, â êîòîðîì îí îïðåäåë¼í, ïîòîìó÷òî ïðåæäå ÷åì ñîáðàòü èñïîëüíÿåìûé ôàéë, ëèíêåðó íåîáõîäèìî íàéòèîïðåäåëåíèå ñèìâîëà è ïîñòàâèòü ñîîòâåòñòâóþùóþ ññûëêó, ãäå èñêàòüýòîò ñèìâîë.Íà îñíîâå ýòèõ çàâèñèìîñòåé ìû áóäåì ñòðîèòü íàïðàâëåííûé ãðàô,êîòîðûé èõ îïèñûâàåò ñëåäóþùèì îáðàçîì. Äîïóñòèì, åñòü áèáëèîòåêàA,çàâèñÿùàÿ îò áèáëèîòåêèB÷åðåç êàêîé-òî ñèìâîë:A → B.Âìåñòîòîãî, ÷òîáû ñëåäèòü çà òåì, êàê óæå ñîáðàííûå áèáëèîòåêè çàâèñÿò äðóãîò äðóãà, ìû áóäåì ðàçáèâàòü áèáëèîòåêè íà îáúåêòíûå ôàéëû, èç êîòîðûõ îíè ñîáðàíû.
Êàæäûé îáúåêòíûé ôàéë áóäåò ïðåäñòàâëåí âåðøèíîéâ íàøåì ãðàôå. мáðà ãðàôà îïèñûâàþò çàâèñèìîñòè ìåæäó îáúåêòíûìè2 Ñèìâîëûìîãóò áûòü îïðåäåëåíû â íåñêîëüêèõ ôàéëàõ. Îíè ëèáî íå ëèíêóþòñÿ âìåñòå, ëè-áî èñïîëüçóþòñÿ ñïåöèàëüíûå îïöèè ëèíîâùèêà, ïîçâîëÿþùèå ïåðåçàïèñûâàòü óæå îïðåäåë¼ííûåñèìâîëû.7ôàéëàìè: åñëè îáúåêòíûé ôàéëo1 çàâèñèò îò îáúåêòíîãî ôàéëà o2 ÷åðåçêàêîé-ëèáî ñèìâîë, òî â ãðàôå áóäåò ðåáðî, íàïðàëåííîå èç âåðøèíûâ âåðøèíóo1o2 .o1 → o2 . ïðîåêòàõ îáúåêòíûå ôàéëû îáúåäèíÿþòñÿ â áèáëèîòåêè, ÷òî ìûáóäåì îòðàæàòü îáúåäèíåíèåì âåðøèí â ãðóïïû.
Òàê, ïðåäûäóùèé ïðèìåð ìîæåò áûòü ðàñøèðåí ñëåäóþùèì îáðàçîì:o3 → o2 ,o4 → o5 ,L1 = [o1 , o3 , o4 ],L2 = [o2 , o5 ].Ïîñëå ââåäåíèÿ ãðóïï íà âåðøèíàõ îíè áóäóò âûãëÿäåòü òàê:[o1 , o3 , o4 ] → [o2 , o5 ].Òàêèì îáðàçîì ñèìâîëüíûå çàâèñèìîñòè â ïðîåêòàõ ìû ïðåäñòàâëÿåìâ âèäå îðèåíòèðîâàííîãî ãðàôà ñ äîïîëíèòåëüíûì îáúåäèíåíèåì âåðøèíâ ãðóïïû.3Äàëåå ìû îïèøåì êàê ìû áóäåì âûäåëÿòü íåîïòèìàëüíûå çàâèñèìîñòè â ïîñòðîåííîì ãðàôå.3 Ýòèãðóïïû ìîãóò áûòü âïîëíå ïðîèçâîëüíûìè, íàïðèìåð îíè ìîãóò ïåðåñåêàòüñÿ.83.2Âûäåëåíèå íåîïòèìàëüíûõ çàâèñèìîñòåé.Ïîñëå òîãî, êàê ãðàô ïîñòðîåí, ìû ìîæåì èññëåäîâàòü åãî íà ñóùåñòâîâàíèå è âûäåëåíèå íåîïòèìàëüíûõ çàâèñèìîñòåé. Àëãîðèòì áóäåòçàêëþ÷àòüñÿ â ñëåäóþùåì.Èç ñïèñêà âñåõ ãðóïï âûáåðåì êàêóþ-íèáóäü ãðóïïóñðåäè ãðóïï, êîòîðûå çàâèñÿò îòâñåõ ãðóïï, îò êîòîðûõ çàâèñèòìû ïîëó÷èì òðîéêóÃðóïïûFèG, âûáåðåì ïðîèçâîëüíóþ ãðóïïó H .
ÒàêF → G → H.H (è ñîîòâåòñòâóþùèå èì áèáëèîòåêè) òðàíçèòèâíî çàâèF, G è Hÿâëÿþòñÿ ãðóïïàìè âåðøèí,ìû õîòèì ïîíÿòü, çàâèñÿò ëè âåðøèíû â ãðóïïåâåðøèíû èçH,FÂî-ïåðâûõ,G âûáåðåì ãðóïïó F , è âî-âòîðûõ, ñðåäèñÿò äðóã îò äðóãà. Âñïîìèíàÿ, ÷òîøèí ãðóïïûG.Fîò êàêèõ-íèáóäü âåð-èëè èíûìè ñëîâàìè, ñóùåñòâóåò ëè ïóòü îò êàêîé-ëèáîäî êàêîé-ëèáî âåðøèíû èçãî ïóòè äà¼ò íàì ïîíÿòü, ÷òî çàâèñèìîñòüãðóïïóGG1 , G2òàê, ÷òîáûH.Íåñóùåñòâîâàíèå ïîäîáíî-F →G→Híåîïòèìàëüíà è(è ñîîòâåòñòâóþùóþ åé áèáëèîòåêó) ìîæíî ðàçäåëèòü íà äâåF → G1 , G1 6→ G2 , G2 → H.Ïñåâäîêîä ïîäîáíîãî àëãîðèòìà ïðåäñòàâëåí íèæå.9Algorithm 1 Ïîèñê íåîïòèìàëüíîé çàâèñèìîñòè.procedure FindUnoptimalDependencies(Graph, Groups)1:2:3:4:5:r ← {}.for G ∈ Groups dofor F ∈ {X ∈ Groups | X → G} dofor H ∈ {Y ∈ Groups | G → Y } doif6:path from11:12:13:toHend if8:10:Fr ← {F, G, H}7:9:Result that is returned from the functionend forend forend forreturn rend procedure10doesn't existthen4Ðåàëèçàöèÿ4.1Âûáîð ëèíêåðà êà÷åñòâå ëèíêåðà, áûë èñïîëüçîâàí ëèíêåð lld, ðàçðàáàòûâàåìûé âðàìêàõ ïðîåêòà LLVM [2].
Ê åãî ïðåèìóùåñòâàì îòíîñèòåëüíî óñòîÿâøåãîñÿ è øèðîêî èñïîëüçóåìîãî ëèíêåðà ld ìîæíî îòíåñòè: ñêîðîñòü lldîò 1.2 äî 2 ðàç áûñòðåå ëèíêåðà gold, êîòîðûé â ñâîþ î÷åðåäü áûñòðååld; îòíîñèòåëüíî ìàëåíüêèé ðàçìåð èñõîäíîãî êîäà ELF ÷àñòü lld íàèþíü 2016 ñîñòàâëÿåò 13k ñòðî÷åê êîäà è COFF ÷àñòü ñîñòàâëÿåò åùå47k , â òî âðåìÿ êàê gold ñîñòàâëÿåò 146k ñòðî÷åê êîäà; ìîäóëüíîñòü èðàñøèðÿåìîñòü â lld îòíîñèòåëüíî ïðîñòî âñòðîèòü äîïîëüíèòåëüíóþëîãèêó, çà ñ÷åò ÷åãî, íàïðèìåð, â lld áûëà äîáàâëåíà òàêàå ôóíêöèÿ êàêäåäóïëèêàöèÿ èäåíòè÷íîãî êîäà. Òàêæå êàê è ëèíêåð gold, lld ìîæíîèñïîëüçîâàòü êàê ïðÿìóþ çàìåíó ld.Áîëåå òîãî, äèçàéí ëèíêåðà, à òî÷íåå âíóòðåííåå ïðåäñòàâëåíèå ôàéëîâ, òàêæå ïîìîãàåò â ðåàëèçàöèè öåëåé äàííîãî èññëåäîâàíèÿ. lld âíóòðè ñåáÿ èñïîëüçóåò ìîäåëü ¾àòîìîâ¿ íåäåëèìûõ êóñêîâ êîäà èëè äàííûõ.
Îáû÷íî êàæäàÿ íàïèñàííàÿ ïîëüçîâàòåëåì ôóíêöèÿ èëè ãëîáàëüíàÿ ïåðåìåííàÿ ýòî àòîì. Êðîìå ýòîãî êîìïèëÿòîð ìîæåò äîáàâëÿòüàòîìû, íàïðèìåð, ñòðîêîâûå ëèòåðàëû èëè íåêîòîðûå êîíñòàíòû.Ïðîñòàÿ hello world ïðîãðàììà âûãëÿäèò òàê:4 çäåñüíå ó÷èòûâàåòñÿ êîä èç ñàìîãî ïðîåêòà LLVM, íà áàçå êîòîðîãî íàïèñàí lld11Àòîìû, òàêæå êàê è ñèìâîëû, ïîìèìî ïðî÷åãî, ìîãóò áûòü îïðåäåë¼ííûìè è íåîïðåäåë¼ííûìè, íåîïðåäåë¼ííûå àòîìû çàâèñÿò îò îïðåäåë¼ííûõ è åñòåñòâåííûì îáðàçîì îáðàçóþò ãðàô çàâèñèìîñòåé. Ýòîò ôàêòïîìîãàåò ïðè ïîñòðåíèè ãðàôà, èñïîëüçóåìîãî â äàííîì èññëåäîâàíèè.124.2Äîïîëíèòåëüíûå ïðîâåðêèÏîñòðîåííàÿ ìîäåëü ÿâëÿåòñÿ äîâîëüíî îáùèì èíñòðóìåíòîì èçó÷åíèÿ çàâèñèìîñòåé â ïðîåêòàõ. Îíà ïîçâîëÿåò ïðèìåíÿòü è äðóãèå àëãîðèòìû íà îðèåíòèðîâàííûõ ãðàôàõ [3].Ñëåäóþùèå àëãîðèòìû áûëè ðåàëèçîâàíû íà îñíîâå äàííîé ìîäåëè:•ïîèñê öèêëîâ,•ïîèñê ìîñòîâ.Ýòè àëãîðèòìû ÿâëÿþòñÿ êëàññè÷åñêèìè àëãîðèòìàìè â òåîðèè ãðàôîâ, è èõ òåîðåòè÷åñêîå îïèñàíèå ìîæíî íàéòè íàïðèìåð â [4].135Îñíîâíûå ðåçóëüòàòûÄëÿ èññëåäîâàíèÿ ýôôåêòèâíîñòè ïðåäëîæåííîãî àëãîðèòìà, áûëèâçÿòû ïðîåêòû ñ îòêðûòûì èñõîäíûì êîäîì, à èìåííî: Qt, SFML, tungsten. Qt [5], â ìîäóëå Qt Tools, áûëà íàéäåíà 1 íåîïòèìàëüíàÿ çàâèñèìîñòü, óëó÷øåíèå êîòîðîé óñêîðÿåò ñáîðêó Qt Tools íà 12%. ïðîåêòå SFML [6] áûëà òàêæå íàéäåíà 1 íåîïòèìàëüíàÿ çàâèñèìîñòü, óëó÷øåíèå êîòîðîé óñêîðÿåò ñáîðêó SFML Window íà 18%. ïðîåêòå Magnum [7] áûëè íàéäåíû íåîïòèìàëüíûå çàâèñèìîñòèâ ìîäóëÿõ MagnumDebugTools è MagnumWavAudioImporter, óëó÷øåíèåêîòîðûõ óñêîðÿåò èõ ñáîðêó íà 11% è 24% ñîîòâåòñòâåííî.Qt Base12%SFML18%Magnum11%, 24%146Çàêëþ÷åíèå ïåðâîé ÷àñòè ðàáîòû áûëî ââåäåíî ïîíÿòèå íåîïòèìàëüíîé çàâèñè-ìîñòè, çàòåì áûëà ðàññìîòðåíà ãðàôîâàÿ ìîäåëü, ïîçâîëÿþùàÿ íàõîäèòüè óñòðàíÿòü ïîäîáíûå çàâèñèìîñòè.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
