Profiling Không Cần Thực Thi: Phương Pháp Mới Trong Lập Trình

Luận văn thạc sĩ nghiên cứu profiling sans exécution, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Bui Nguyen-Minh
• Người hướng dẫn: Professeur Danny Dubé
• Trường học: Université Laval
• Chuyên ngành: Informatique
• Đề tài: Phương Pháp Profiling Không Cần Thực Thi Trong Lập Trình
• Loại tài liệu: Mémoire
• Năm xuất bản: 2006
• Địa điểm: Québec

Tóm tắt

I. Giới Thiệu Phương Pháp Profiling Không Cần Thực Thi

Profiling là công cụ quan trọng để phân tích hành vi chương trình. Nó giúp hiểu cách chương trình hoạt động, từ đó tối ưu hóa hiệu suất. Các nhà sản xuất phần cứng sử dụng profiling để đánh giá hiệu năng trên kiến trúc mới. Lập trình viên dùng nó để xác định những phần code quan trọng cần cải thiện. Các trình biên dịch sử dụng profiling để đo lường hiệu quả của các thuật toán tối ưu hóa. Thông thường, profiling được thực hiện bằng cách thêm code vào chương trình và chạy nó. Tuy nhiên, có một phương pháp khác: Profiling không cần thực thi.

1.1. Tổng Quan Về Kỹ Thuật Profiling Tĩnh

Profiling tĩnh là một phương pháp phân tích chương trình mà không cần chạy chương trình đó. Nó khác với profiling động, là phương pháp đo lường hành vi của chương trình trong quá trình chạy. Profiling tĩnh sử dụng các kỹ thuật phân tích code để suy ra thông tin về cách chương trình sẽ hoạt động. Điều này có thể bao gồm việc xác định tần suất và thời lượng của các lệnh gọi hàm. Lợi ích của profiling tĩnh là nó có thể được thực hiện trước khi chương trình được chạy, giúp xác định vấn đề tiềm ẩn sớm. Theo tài liệu gốc, "Analysestatiquedeprogrammesestunefamilledetechniquespermet-tantdedériverdesrésultatssurl’exécutiondeprogrammessansexécutercesderniers."

1.2. Ưu Điểm và Nhược Điểm của Profiling Tĩnh

Profiling tĩnh có một số ưu điểm so với profiling động. Nó không yêu cầu chạy chương trình, vì vậy nó có thể được sử dụng cho các chương trình mà không thể chạy được (ví dụ: do thiếu tài nguyên hoặc phụ thuộc). Nó cũng có thể cung cấp thông tin chi tiết hơn về hành vi của chương trình. Tuy nhiên, profiling tĩnh cũng có những hạn chế. Nó có thể khó thực hiện và có thể không chính xác nếu chương trình sử dụng các tính năng phức tạp (ví dụ: đa luồng, reflection). Một nhược điểm khác là nó không thể đo lường hiệu suất thực tế của chương trình, chỉ là ước tính.

II. Vấn Đề và Thách Thức Của Profiling Không Thực Thi

Profiling không thực thi gặp nhiều vấn đề. Quá trình mô hình hóa chương trình là một thách thức. Việc giải quyết hệ thống mô hình cũng không đơn giản. Sự hội tụ của hệ thống là một vấn đề cần giải quyết. Cuối cùng, việc đánh giá kết quả profiling là một khó khăn. Mô hình hóa chương trình một cách chính xác là bước quan trọng nhất. Sự phức tạp của code, đặc biệt là với các ngôn ngữ như C, gây nhiều khó khăn.

2.1. Khó Khăn Trong Việc Mô Hình Hóa Chương Trình

Mô hình hóa chương trình là bước đầu tiên và quan trọng nhất trong profiling không thực thi. Cần tạo ra một hệ thống mô tả chính xác hành vi của chương trình. Điều này có thể rất khó khăn, đặc biệt là với các ngôn ngữ phức tạp như C. Các chương trình có thể có nhiều nhánh rẽ, vòng lặp và lệnh gọi hàm, điều này khiến việc tạo ra một mô hình chính xác trở nên khó khăn hơn. Việc thiếu các hiệu ứng phụ trong lập trình hàm giúp mô hình hóa dễ dàng hơn. "Enlaprogrammationfonctionnelle,ons’affranchitdefaçonradicaledeseffetsdebordeninterdisanttouteopérationd’assignation."

2.2. Vấn Đề Hội Tụ Hệ Thống Trong Profiling Tĩnh

Khi mô hình hóa chương trình, ta thường xây dựng một hệ thống các phương trình. Việc giải hệ thống này có thể là một thách thức. Hệ thống có thể không hội tụ, có nghĩa là không có giải pháp duy nhất. Hoặc, hệ thống có thể hội tụ đến một giải pháp không chính xác. Việc đảm bảo rằng hệ thống hội tụ và hội tụ đến một giải pháp chính xác là rất quan trọng để có được kết quả profiling chính xác. Các phương pháp lặp (iterative) thường được sử dụng để giải quyết các hệ thống này, và việc lựa chọn phương pháp phù hợp là rất quan trọng.

III. Cách Xây Dựng Mô Hình Thực Thi Cho Profiling Tĩnh

Phương pháp profiling không thực thi xây dựng một hệ thống mô hình hóa sự thực thi của chương trình. Sau đó, nó tính toán profile dựa trên kết quả thu được khi giải hệ thống. Trong giai đoạn thứ hai, sử dụng kết quả từ giai đoạn đầu, nó xây dựng và giải một hệ phương trình để có được kết quả chi tiết hơn. Việc sử dụng các ngôn ngữ lập trình hàm giúp đơn giản hóa quá trình này. Lập trình hàm tránh các tác dụng phụ, làm cho code dễ phân tích hơn.

3.1. Lợi Ích của Lập Trình Hàm Trong Profiling Tĩnh

Lập trình hàm rất phù hợp với profiling tĩnh vì nó tránh các tác dụng phụ. Trong lập trình hàm, các hàm chỉ nhận đầu vào và trả về đầu ra, không thay đổi trạng thái bên ngoài. Điều này làm cho code dễ phân tích hơn vì ta không cần lo lắng về các hiệu ứng phụ không mong muốn. Sự vắng mặt của các hiệu ứng phụ giúp việc xây dựng mô hình chính xác hơn. "C’estpourcetteraisonqu’onpeutéviterleseffetsdebordenutilisantce3 typedelangage."

3.2. Sử Dụng Tính Trong Suốt Tham Chiếu Để Tối Ưu Profiling

Tính trong suốt tham chiếu là một thuộc tính quan trọng của lập trình hàm. Nó có nghĩa là một biểu thức có thể được thay thế bằng giá trị của nó mà không ảnh hưởng đến kết quả của chương trình. Điều này cho phép các trình biên dịch thực hiện các tối ưu hóa, chẳng hạn như loại bỏ các lệnh gọi hàm không cần thiết. Profiling tĩnh có thể được hưởng lợi từ tính trong suốt tham chiếu vì nó giúp đơn giản hóa quá trình phân tích code.

IV. Giải Hệ Phương Trình Để Ước Tính Profile Chương Trình

Sau khi xây dựng mô hình chương trình, bước tiếp theo là giải hệ phương trình. Hệ phương trình này mô tả mối quan hệ giữa các phần khác nhau của chương trình. Việc giải hệ phương trình này cho phép ta ước tính profile của chương trình. Các phương pháp lặp, như phương pháp Gauss-Seidel, thường được sử dụng để giải các hệ phương trình này. Tuy nhiên, cần đảm bảo rằng hệ thống hội tụ để có được kết quả chính xác.

4.1. Phương Pháp Gauss Seidel Trong Giải Hệ Phương Trình

Phương pháp Gauss-Seidel là một phương pháp lặp để giải hệ phương trình tuyến tính. Nó bắt đầu với một ước tính ban đầu của giải pháp và sau đó lặp lại cho đến khi giải pháp hội tụ. Trong mỗi lần lặp, phương pháp Gauss-Seidel sử dụng các giá trị mới nhất của các biến để tính toán các giá trị tiếp theo. Mặc dù đơn giản, Gauss-Seidel không phải lúc nào cũng hội tụ.

4.2. Điều Kiện Hội Tụ Cho Phương Pháp Gauss Seidel

Để phương pháp Gauss-Seidel hội tụ, hệ phương trình phải đáp ứng một số điều kiện. Một điều kiện đủ là ma trận hệ số phải là ma trận đường chéo trội. Điều này có nghĩa là giá trị tuyệt đối của phần tử trên đường chéo trong mỗi hàng phải lớn hơn tổng giá trị tuyệt đối của các phần tử còn lại trong hàng đó. Nếu hệ phương trình không đáp ứng điều kiện này, phương pháp Gauss-Seidel có thể không hội tụ. Các phương pháp khác có thể được sử dụng trong trường hợp đó.

V. Phân Tích Trừu Tượng Trong Profiling Không Cần Thực Thi

Phân tích trừu tượng được sử dụng để ước lượng các giá trị của các biểu thức trong chương trình. Mỗi biểu thức được gán một nhãn duy nhất. Các giá trị trừu tượng được định nghĩa, bao gồm các giá trị boolean, cặp, hàm, lỗi và giá trị vô hạn. Một tập hợp các giá trị mà biểu thức có thể trả về được xác định cho mỗi nhãn. Ví dụ, giá trị của (cons #f #f) là P (cặp). Giá trị của (call #f #f) là ERROR.

5.1. Định Nghĩa Các Giá Trị Trừu Tượng

Các giá trị trừu tượng được định nghĩa để đơn giản hóa quá trình phân tích. Các giá trị này bao gồm #f (false), P (cặp), λ (hàm), ERROR (lỗi) và ⊥ (giá trị vô hạn). Mục đích là để biểu diễn các giá trị có thể của các biểu thức mà không cần phải tính toán chúng một cách chính xác. Ví dụ, thay vì tính toán giá trị của một biểu thức phức tạp, ta chỉ cần biết liệu nó có thể trả về một lỗi hay không.

5.2. Loại Bỏ Code Chết Bằng Phân Tích Trừu Tượng

Phân tích trừu tượng có thể được sử dụng để loại bỏ code chết, tức là các phần code không bao giờ được thực thi. Bằng cách xác định các biểu thức không bao giờ được thực thi, ta có thể loại bỏ chúng khỏi chương trình. Điều này có thể giúp cải thiện hiệu suất và giảm kích thước của chương trình. Một giá trị boolean được sử dụng để chỉ ra liệu một biểu thức có được thực thi hay không.

VI. Ứng Dụng và Tương Lai Của Profiling Không Thực Thi

Profiling không thực thi có tiềm năng lớn trong nhiều lĩnh vực. Nó có thể được sử dụng để tối ưu hóa hiệu suất của chương trình, phát hiện lỗi và cải thiện bảo mật. Trong tương lai, profiling không thực thi có thể trở nên quan trọng hơn khi các chương trình trở nên phức tạp hơn. Các nghiên cứu tiếp theo tập trung vào việc cải thiện độ chính xác và hiệu quả của phương pháp. Cần nhiều nỗ lực hơn để áp dụng phương pháp này cho các ngôn ngữ thực tế và các chương trình lớn.

6.1. Tiềm Năng Phát Triển Của Profiling Tĩnh

Mặc dù profiling tĩnh đã được nghiên cứu trong nhiều năm, nhưng vẫn còn nhiều tiềm năng phát triển. Các kỹ thuật mới đang được phát triển để cải thiện độ chính xác và hiệu quả của profiling tĩnh. Ví dụ, các kỹ thuật học máy có thể được sử dụng để học các mô hình chính xác hơn về hành vi của chương trình. Việc tích hợp profiling tĩnh vào các công cụ phát triển phần mềm có thể giúp lập trình viên viết code hiệu quả hơn.

6.2. Hướng Nghiên Cứu Tiếp Theo Trong Profiling Tĩnh

Có một số hướng nghiên cứu quan trọng trong profiling tĩnh. Một là cải thiện độ chính xác của các mô hình. Hai là mở rộng các kỹ thuật cho các ngôn ngữ và chương trình phức tạp hơn. Ba là phát triển các công cụ hỗ trợ profiling tĩnh một cách dễ dàng hơn. Cuối cùng, việc kết hợp profiling tĩnh với các kỹ thuật tối ưu hóa khác có thể mang lại những cải tiến đáng kể về hiệu suất.

Trích đoạn nội dung tài liệu

PROFILING SANS EXÉCUTION Mémoire de fin d’études Master d’Informatique Etudiant : BUI Nguyen-Minh Sous la direction de : Professeur Danny DUBÉ Département d’informatique, Université LAVAL Institute de la Francophonie pour l’Informatique Novembre 2006 TIEU LUAN MOI download : [e-mail] Remerciements Je voudrais remercier professeur Danny Dubé au Département d’Infor- matique et de Génie Logiciel à l’Université Laval pour tout ce qu’il a fait pour moi pendant mon stage, même je n’étais pas très autonome. Je tiens également à remercier tous les professeurs à l’IFI. Merci à mes parents et mes amis. 1 TIEU LUAN MOI download : [e-mail] Résumé Dans cette mémoire, nous voudrions présenter une autre façon pour faire le profiling.

Les méthodes courantes, en général, elles ajoutent quelques mor- ceaux de code sources et exécutent le programme pour calculer le profil d’un programme. Par contre, notre méthode, elle n’exécute pas le programme mais essaye de construire un système qui modèle l’exécution du programme puis calcule le profil basé sur le résultat obtenu quand on résout le système. Cette méthode se compose de deux phases. La première phase vise à calcul le résul- tat abstrait en utilisant un système de contrainte.

Dans la deuxième phase, utilisant le résultat de la première phase, on construit et résout un système d’équation pour obtenir un résultat plus détaillé. Pourtant, la méthode de profiling sans exécution reste de nombreux de problèmes sur le processus de la modélisation le programme, la solution le système, la convergence du système et l’évaluation. Nous abordons aussi quelques idées générales sur le langage fonctionnel et le langage de programmation Scheme. TIEU LUAN MOI download : [e-mail] Table des matières 1 Introduction 1 1.2 Types de profiling .3 Sujet de stage .2 Particularité des langages fonctionnels .1 Absence des effets de bord .3 Peu de structures de contrôle .4 Fonctions comme objets de première classe .5 Gestion de la mémoire de façon automatiquement .2 La syntaxe du lambda calcul .2 Analyse de jetons .3 L’algorithme en bref .3 Génération des contraintes.

17 i TIEU LUAN MOI download : [e-mail] 5 Analyse statique 19 5.1 Règles pour calculer Πl : .2 Règles pour calculer Πx : .3 Règles pour calculer χl et Kl (l0 ) : .3 Vérifier les équations .4 Résoudre le système d’équations. 31 6 Conclusion 34 ii TIEU LUAN MOI download : [e-mail] Chapitre 1 Introduction 1.1 Profiling Les outils pour analyser les programmes (profiling) jouent un rôle très im- portant dans la compréhension des comportements des programmes. En effet, les constructeurs de matériel informatique ont en besoin pour évaluer com- ment les programmes marcheront dans la nouvelle architecture. Ils sont aussi indispensables pour les programmeurs dans l’analyse de leurs codes sources et dans l’identification des morceaux importants.

D’autre part, le profiling est considéré, par les compilateurs, un outil de mesurer les algorithmes d’op- timisation.2 Types de profiling En général, il y a deux types de profiling : Analyse statique de programmes et analyse dynamique de programmes. L’analyse statique de programmes est une famille de techniques permet- tant de dériver des résultats sur l’exécution de programmes sans exécuter ces derniers. Elle se distingue ainsi de l’analyse dynamique ou test, qui revient à essayer le programme sur différentes entrées jugées représentatives, afin de vérifier s’il produit les résultats attendus sur ces entrées. L’analyse dynamique de programmes est une famille de techniques d’ana- lyse d’exécution qui mesure le comportement d’un programme, en particulier la fréquence et la durée des appels de fonction, quand il fonctionne.

La sortie est une suite des événements enregistrés (une trace) ou d’un résumé statis- tique des événements observés (un profil ) 1 TIEU LUAN MOI download : [e-mail] Actuellement, il existe un bon nombre de logiciels qui permettent de faire l’analyse dynamique de programmes, par exemple : grof, ATOM. Les profileurs emploient une grande variété de techniques pour rassembler des données, y compris des interruptions, l’instrumentation de code, des hooks de système d’exploitation, et des compteurs d’exécution. L’instrumentation de code, au temps de la compilation, il insère le code dans le programme à analyser. Alors le code inséré produit des données d’ana- lyse.

Le logiciel ATOM utilise cette technique.3 Sujet de stage Notre stage a le profiling sans exécution comme le sujet principal. Cette méthode de profiling consiste à essayer d’estimer le résultat d’un programme et de mesurer ses comportements sans exécuter le programme. 2 TIEU LUAN MOI download : [e-mail] Chapitre 2 Langage fonctionnel 2.1 Concepts Il y a trois types de langage de programmation : Programmation impé- rative, programmation fonctionnelle et programmation logistique. La programmation logique est une forme de programmation dont l’essence est de définir des règles de logique mathématique au lieu de fournir une succession d’instructions que l’ordinateur exécuterait.

Le premier langage de programmation logique est Prolog. La programmation impérative est le style de programmation le plus uti- lisé, dans lequel les instructions qui modifient les données sont exécutées simplement les unes après les autres, avec quelques structures de contrôle permettant de créer des boucles ou des alternatives. Le troisième type de langage de programmation est le style de programma- tion dans lequel on ne programme qu’en écrivant des fonctions qui appellent d’autres fonctions. Ce paradigme de programmation fournie une abstraction très puissante et très bien connue en mathématiques : la fonction.2 Particularité des langages fonctionnels 2.1 Absence des effets de bord Dans la programmation fonctionnelle, on s’affranchit de façon radicale des effets de bord en interdisant toute opération d’assignation.

La programmation fonctionnelle souligne l’application des fonctions, contrai- rement à la programmation impérative qui met l’accent sur les changements d’état et l’exécution des commandes séquentielles. C’est pour cette raison qu’on peut éviter les effets de bord en utilisant ce 3 TIEU LUAN MOI download : [e-mail] type de langage. En effet, pour décrire un programme, au lieu d’une machine d’états, le paradigme fonctionnel utilise un emboîtement de fonctions consi- déré comme des boîtes noires qui sont imbriquées les unes dans les autres. L’effet de bord est un effet dans lequel une fonction modifie un état autre que sa valeur de retour.

Par exemple une fonction change la valeur d’une variable globale, donc quand on exécute cette fonction on peut obtenir deux résultats différents. int x = 0 ; int getx() { x++ ; return x ; } Cela rende souvent le comportement des programmes plus difficile à com- prendre.2 Transparence référentielle Une autre propriété liée à la programmation fonctionnelle, c’est la trans- parence référentielle. Une expression est transparente de manière référentielle si elle peut être remplacée dans le code source de programme sans changer le résultat final du programme. En d’autres termes, cela résulte en un pro- gramme avec les même effets et sorties pour les mêmes entrées.

Un grand avantage d’écrire du code avec un style référentiellement trans- parent est que l’analyse de code statique est plus facile et que des transforma- tions d’amélioration de code sont automatiquement possibles. Par exemple, en programmation en C, il y a une pénalité de performance pour l’inclusion d’une fonction dans une boucle, même si l’appel de fonction pourrait être dé- placé à l’extérieur de la boucle sans changer les résultats du programme. Le programmeur pourrait être forcé à faire ce déplacement, peut-être au dépend de la lisibilité du code. Mais, si le compilateur est capable de déterminer si l’appel de la fonction est référentiellement transparent, il peut alors effectuer automatiquement cette transformation.

int square(int x) { return (x*x) ; } 4 TIEU LUAN MOI download : [e-mail] Donc, ce morceau de code : int foo(int n) { for (int i = 0 ; i <n ; i++) printf(square (5)) ; } peut être remplacé par int foo(int n) { int y = square (5) ; for (int i = 0 ; i <n ; i++) printf(y) ; } 2.3 Peu de structures de contrôle Contrairement aux langages impératifs, dans les langages fonctionnels, les structures de contrôle sont utilisées de façon moins fréquente que les fonctions récursives. Par exemple la fonction pour calculer une somme en C : sum = 0 ; for (i :=1 ; i<n ; i++) sum += i ; est récrite en Scheme : (let loop ((i 0)) (if (= i n) 0 (+ i (loop (+ i 1))))) 5 TIEU LUAN MOI download : skknchat@gmail.4 Fonctions comme objets de première classe Les langages fonctionnels traitent les fonctions en tant qu’objets de pre- mière classe. Spécifiquement, ceci signifie que des fonctions peuvent être créées pendant l’exécution d’un programme, être stockées en structures de données, passer comme arguments à d’autres fonctions, et retourner comme valeurs d’autres fonctions. Par exemple : Création des fonctions à la volée : (set ! f (lambda (x) (+ x 1))) Passage en argument, retour comme résultat : (f c (lambda (x) (g (+ x 1)))) Stockage dans les structures de données et extraction des structures de don- nées : (define lst (list 1 (lambda (x) ( + x 1)))) (set ! f (list-ref lst 1)) 2.5 Gestion de la mémoire de façon automatiquement Dans les langages fonctionnels, on utilise la gestion automatiquement de la mémoire, donc, ces langages sont généralement plus sécuritaires mais ils prennent plus de mémoire par rapport aux langages impératifs comme C.1 Idées générales Le lambda calcul a été inventé par le logicien américain Alonzo Church dans les années 1930.

Le lambda calcul joue un rôle très important dans les langages fonctionnels parce que la fonction est le centrale dans les langages fonctionnels. Dans le calcul de lambda, chaque expression représente une fonction avec un argument simple. Une fonction est anonyme définie par une expression de lambda qui exprime l’application de la fonction sur son argument. Par exemple, ajouter-deux la fonction f tels que f (x) = x + 2 serait exprimé en calcul de lambda comme λx.x + 2 (ou d’une manière équivalente comme λy.y +2, le nom de l’argument formel est peu important) et le nombre f (3) serait écrit en tant que (λx.x + 2)3 6 TIEU LUAN MOI download : [e-mail] L’application de fonction est associative à gauche : f xy = (f x)y.

Considérer la fonction qui prend une fonction comme argument et s’applique avec la valeur de 3 : λf. Cette dernière fonction pourrait être appliquée à notre plutôt ajoutent-deux la fonction comme suit : (λf. Donc les trois expressions (λf.x + 2)3 et 3 + 2 sont équivalentes. Une fonction de deux variables est exprimée en calcul de lambda en fonc- tion d’un argument qui renvoie une fonction d’un argument.

Par exemple, la fonction f (x, y) = x − y serait écrite comme λy.x − y Les trois expressions (λyx.7−y)2 et 7−2 sont équivalentes. C’est cette équivalence des expressions de lambda qui en général ne peuvent pas être décidées par un algorithme. Les expressions de lambda ne peuvent pas toutes être réduites à une valeur définie comme celle ci-dessus ; considérer par exemple (λx. Tandis que le calcul de lambda lui-même ne contient pas des symboles pour les nombres entiers ou l’addition, ceux-ci peuvent être définis comme abréviations dans le calcul.2 La syntaxe du lambda calcul Les trois constructions principales du lambda calcul sont – La variable, par exemple : x, y, z.

– L’application : si u et v sont deux programmes, on peut considérer u comme une fonction et v comme un argument possible, et former l’application uv. – l’abstraction : si u est un programme dépendant (ou non) de la variable x, alors on peut former un nouveau programme λx.u, qui représente la fonction qui prend la variable x et retourne u. D’une autre manière, on peut définir lambdaŰcalcul en utilisant la défi- nition formelle grammaire hors-contexte BNF < expr >::=< identif ier > < expr >::= (λ < identif ier >. < expr >) < expr >::= (< expr >< expr >) En lambda calcul, l’évaluation se fait à l’aide de réductions.

Les deux réductions dont nous aurons besoin sont l’alpha - réduction qui est l’équi- valent du renommage de variable et la bêta - réduction, qui est l’équivalent de l’appel de fonction.