Все права на текст принадлежат автору: Примож Габриэльчич.
Это короткий фрагмент для ознакомления с книгой.
Высокая производительность Delphi (черновик перевода главы 1)Примож Габриэльчич

Примож Габриэльчич ВЫСОКАЯ ПРОИЗВОДИТЕЛЬНОСТЬ DELPHI Создание быстрых приложений на Delphi с использованием конкурентности, параллельного программирования и управления памятью

BIRMINGHAM - MUMBAI


Copyright © 2018 Packt Publishing

All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews.

Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book.

Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information.


Commissioning Editor: Merint Mathew

Acquisition Editor: Nitin Dasan

Content Development Editor: Nikhil Borkar

Technical Editor: Jijo Maliyekal

Copy Editor: Safis Editing

Project Coordinator: Ulhas Kambali

Proofreader: Safis Editing

Indexer: Mariammal Chettiyar

Graphics: Tania Dutta

Production Coordinator: Deepika Naik


First published: February 2018

Production reference: 1230218

Published by Packt Publishing Ltd.


Livery Place

35 Livery Street

Birmingham


B3 2PB, UK.

ISBN 978-1-78862-545-6

www.packtpub.com


mapt.io

Mapt is an online digital library that gives you full access to over 5,000 books and videos, as well as industry leading tools to help you plan your personal development and advance your career. For more information, please visit our website.

Why subscribe?

Spend less time learning and more time coding with practical eBooks and Videos from over 4,000 industry professionals

Improve your learning with Skill Plans built especially for you

Get a free eBook or video every month

Mapt is fully searchable

Copy and paste, print, and bookmark content

PacktPub.com

Did you know that Packt offers eBook versions of every book published, with PDF and ePub files available? You can upgrade to the eBook version at www.PacktPub.com and as a print book customer, you are entitled to a discount on the eBook copy. Get in touch with us at service@packtpub.com for more details.

At www.PacktPub.com, you can also read a collection of free technical articles, sign up for a range of free newsletters, and receive exclusive discounts and offers on Packt books and eBooks.

Contributors

Об авторе

Primož Gabrijelčič started coding in Pascal on 8-bit micros in the 1980s and he never looked back. In the last 20 years, he was mostly programming high-availability server applications used in the broadcasting industry. A result of this focus was the open sourced parallel programming library for Delphi—OmniThreadLibrary. He's also an avid writer and has written several hundred articles, and he is a frequent speaker at Delphi conferences where he likes to talk about complicated topics, ranging from memory management to creating custom compilers.

Примож Габриелчич начал кодировать на Паскале на 8-битных микрокомпьютерах в 1980-х годах и никогда не оглядывался назад. В последние 20 лет он в основном программировал серверные приложения с высокой доступностью(?), используемые в индустрии вещания. Результатом этого внимания стала библиотека параллельного программирования с открытым исходным кодом для Delphi — OmniThreadLibrary. Он также заядлый писатель, написал несколько сотен статей и часто выступает на конференциях Delphi, где любит говорить на сложные темы, начиная от управления памятью и заканчивая созданием пользовательских компиляторов.

About the reviewers

Stefan Glienke, since his very first steps with Turbo Pascal in school, was passionate about programming. In his spare time, he worked at a software company using Visual Basic and started learning C++ and Delphi and decided to start an apprenticeship as a software developer after graduation.

Over the years, he developed an interest in software architecture and began helping fellow developers improve their skills, participating in several open source projects, such as Spring4D. He is also the author of TestInsight.

Stefan has worked as reviewer on the books Coding in Delphi and Dependency Injection in Delphi.

I'd like to thank Primoz for writing this incredible book and suggesting me as a technical reviewer. I'd also like to thank Nitin Dasan and Ulhas Kambali from Packt for their help and patience. Also, big thanks go to my parents who helped me with my relocation, which was happening at the same time as I was doing this review.


Bruce McGee is the founder of Glooscap Software, a software development and consulting company in Toronto, Ontario. He is also a long-time Delphi user, which he continues to work with every day.

Packt is searching for authors like you

If you're interested in becoming an author for Packt, please visit authors.packtpub.com and apply today. We have worked with thousands of developers and tech professionals, just like you, to help them share their insight with the global tech community. You can make a general application, apply for a specific hot topic that we are recruiting an author for, or submit your own idea.

Table of Contents

Title Page

Copyright and Credits

Delphi High Performance

Packt Upsell

Why subscribe?

PacktPub.com

Contributors

About the author

About the reviewers

Packt is searching for authors like you

Preface

Who this book is for

What this book covers

To get the most out of this book

Download the example code files

Conventions used

Get in touch

Reviews

About Performance

What is performance?

Different types of speed

Algorithm complexity

Big O and Delphi data structures

Data structures in practice

Mr. Smith's first program

Looking at code through the Big O eyes

Don't guess, measure!

Profiling with TStopwatch

Profilers

AsmProfiler

Sampling Profiler

AQTime

Nexus Quality Suite

Summary

Fixing the Algorithm

Responsive user interfaces

Updating a progress bar

Bulk updates

Virtual display

Caching

Dynamic cache

Speeding up SlowCode

Summary

Fine-Tuning the Code

Delphi compiler settings

Code inlining control

Optimization

Record field alignment

Assertions

Overflow checking

Range checking

Extracting common expressions

The helpful CPU window

Behind the scenes

A plethora of types

Simple types

Strings

Arrays

Records

Classes

Interfaces

Optimizing method calls

Parameter passing

Method inlining

The magic of pointers

Going the assembler way

Returning to SlowCode

Summary

Memory Management

Optimizing strings and array allocations

Memory management functions

Dynamic record allocation

FastMM internals

Memory allocation in a parallel world

Replacing the default memory manager

ScaleMM

TBBMalloc

Fine-tuning SlowCode

Summary

Getting Started with the Parallel World

Processes and threads

When to parallelize the code?

Most common problems

Never access UI from a background thread

Simultaneous reading and writing

Sharing a variable

Synchronization

Critical sections

Other locking mechanisms

A short note on coding style

Shared data with built-in locking

Interlocked operations

Object life cycle

Communication

Windows messages

Synchronize and Queue

Polling

Performance

Third-party libraries

Summary

Working with Parallel Tools

TThread

Advanced TThread

Setting up a communication channel

Sending messages from a thread

Implementing a timer

Summary

Exploring Parallel Practices

Tasks and patterns

Variable capturing

Tasks

Exceptions in tasks

Parallelizing a loop

Thread pooling

Async/Await

Join

Join/Await

Future

Parallel for

Pipelines

Creating the pipeline

Stages

Displaying the result and shutting down

Summary

Using External Libraries

Using object files

Object file formats

Object file linking in practice

Using C++ libraries

Using a proxy DLL in Delphi

Summary

Best Practices

About performance

Fixing the algorithm

Fine-tuning the code

Memory management

Getting started with the parallel world

Working with parallel tools

Exploring parallel practices

Using external libraries

Final words

Other Books You May Enjoy

Leave a review - let other readers know what you think

Preface

Performance matters!

I started programming on 8-bit micros, and boy, was that an interesting time! Memory was typically not a problem as we didn't write big programs, but they certainly weren't running fast, especially if you run them with a built-in BASIC interpreter. It is not surprising that I quickly learned assembler and spent lots of early years shifting bits and registers around. So did almost everybody else who wanted to release a commercial application written for one of those computers. There were, more or less, no games and applications written in BASIC simply because they would run too slow and nobody would use them.

Time has changed; computers are now fast—incredibly fast! If you don't believe me, check the code examples for this book. A lot of times, I had to write loops that spin over many million iterations so that the result of changing the code would be noticed at all. The raw speed of processors has also changed the software development world. Low-level languages such as assembler and C mostly gave way to more abstract approaches—C#, C++, Delphi, F#, Java, Python, Ruby, JavaScript, Go, and so on. The choice is yours. Almost anything you write in these languages runs fast or at least fast enough.

Computers are so fast that we sometimes forget the basic rule—performance matters. Customers like programs that operate so fast that they don't have to think about it. If they have to wait 10 seconds for a form to appear after clicking on a button, they won't be very happy. They'll probably still use the software, though, provided that it works for them and doesn't crash. On the other hand, if you write a data processing application that needs 26 hours for a job that executes daily, you'll certainly lose them.

I'm not saying that you should switch to assembler. Low-level languages are fast, but coding in them is too slow for modern times, and the probability of introducing bugs is just too high. High-level languages are just fine, but you have to know how to use them. You have to know what is fast and what not and—preferably—you should take this into account when designing the code.

This book will walk you through the different approaches that will help you write better code. Writing fast code is not the same as optimizing a few lines of your program to the extreme. Most of the time, that is in fact the completely wrong approach! However, I'm getting ahead of myself. Let the book speak for itself.

Who this book is for

This book was written for all Delphi programmers out there. You will find something interesting inside, whether you are new to programming or a seasoned old soul. I'm talking about basic stuff, about strings and arrays, lists and objects, but I'm also discussing parallel programming, memory manager internals, and object linking. There is also plenty of dictionaries, pointers, algorithmic complexities, code inlining, parameter passing, and what not.

So, whoever you are, dear reader, I'm pretty sure you'll find something new in this book. Enjoy!

What this book covers

Chapter 1, About Performance, talks about performance. We'll dissect the term itself and try to find out what users actually mean when they say that a program is performing (or not performing) well. Then, we will move into the area of algorithm complexity. We'll skip all the boring mathematics and just mention the parts relevant to programming. We will also look at different ways of finding the slow (non-performant) parts of the program, from pure guesswork to measuring tools of a different sophistication, homemade and commercial.

Chapter 2, Fixing the Algorithm, examines a few practical examples where changing an algorithm can speed up a program dramatically. In the first part, we'll look at graphical user interfaces and what we can do when a simple update to TListBox takes too long. The second part of the chapter explores the idea of caching and presents a reusable caching class with very fast implementation. In the last part, we'll revisit some code from Chapter 1, About Performance, and make it faster, again, by changing an algorithm.

Chapter 3, Fine-Tuning the Code, deals with lots of small things. Sometimes, performance lies in many small details, and this chapter shows how to use them to your advantage. We'll check the Delphi compiler settings and see which ones affect the code speed. We'll look at the implementation details for built-in data types and method calls. Using a correct type in a right way can mean a lot. Of course, we won't forget about the practical side. This chapter will give examples of different optimization techniques, such as extracting common expressions, using pointers to manipulate data, and implementing parts of the solution in assembler. At the end, we'll revisit the code from Chapter 1, About Performance, and make it even faster.

Chapter 4, Memory Management, is all about memory. It starts with a discussion on strings, arrays, and how their memory is managed. After that, we will move to the memory functions exposed by Delphi. We'll see how we can use them to manage memory. Next, we'll cover records—how to allocate them, how to initialize them, and how to create useful dynamically-allocated generic records. We'll then move into the murky waters of memory manager implementation. I'll sketch a very rough overview of FastMM, the default memory manager in Delphi. First, I'll explain why FastMM is excellent and then I'll show when and why it may slow you down. We'll see how to analyze memory performance problems and how to switch the memory manager for a different one. In the last part, we'll revisit the SlowCode program and reduce the number of memory allocations it makes.

Chapter 5, Getting Started with the Parallel World, moves the topic to parallel programming. In the introduction, I'll talk about processes and threads, and multithreading and multitasking to establish some common ground for discussion. After that, you'll start learning what not to do when writing parallel code. I'll explain how the user interface must be handled from background threads and what problems are caused by sharing data between threads. Then, I'll start fixing those problems by implementing various kinds of synchronization mechanisms and interlocked operations. We'll also deal with the biggest problem synchronization brings to the code—deadlocking. As synchronization inevitably slows the program down, I'll explain how to achieve the highest possible speed using data duplication, aggregation, and communication. At the end, I'll introduce two third-party libraries that contain helpful parallel functions and data structures.

Chapter 6, Working with Parallel Tools, focuses on a single topic, Delphi's TThread class. In the introduction, I'll explain why I believe that TThread is still important even in this modern age. I will explore different ways in which TThread based threads can be managed in your code. After that, I'll go through the most important TThread methods and properties and explain what they're good for. In the second part of the chapter, I'll extend TThread into something more modern and easier to use. Firstly, I'll add a communication channel so that you'll be able to send messages to the thread. After that, I'll implement a derived class designed to handle one specific usage pattern and show how this approach simplifies writing parallel code to the extreme.

Chapter 7, Exploring Parallel Practices, moves the multithreaded programming to more abstract terms. In this chapter, I'll discuss modern multithreading concepts: tasks and patterns. I'll look into Delphi's own implementation, Parallel Programming Library, and demonstrate the use of TTask/ITask. We'll look at topics such as task management, exception handling, and thread pooling. After that, I'll move on to patterns and talk about all Parallel Programming Library patterns: Join, Future, and Parallel For. I will also introduce two custom patterns—Async/Await and Join/Await—and finish the chapter with a discussion on the Pipeline pattern from OmniThreadLibrary.

Chapter 8, Using External Libraries, admits that sometimes Delphi is not enough. Sometimes the problem is too complicated to be efficiently solved by a human. Sometimes Pascal is just lacking the speed. In such cases, we can try finding an existing library that solves our problem. In most cases, it will not support Delphi directly but will provide some kind of C or C++ interface. This chapter looks into linking with C object files and describes typical problems that you'll encounter on the way. In the second half, I'll present a complete example of linking to a C++ library, from writing a proxy DLL to using it in Delphi.

Chapter 9, Best Practices, wraps it all up. In this last chapter, I'll revisit all the important topics I explored in previous chapters. At the same time, I'll drop in some additional tips, tricks, and techniques.

To get the most out of this book

Although you can read this book in bed or on the beach, you will need a computer and Delphi to play with the code examples. The code was written in Delphi 10.2 Tokyo, but it should also work without a problem in the older versions. I did use some modern features in demos—and dedicated a chapter to Parallel Programming Library that was introduced in Delphi XE7—so anything older than that is hit and miss.

This book does not refer to any functionality specific to the Enterprise edition. You'll be able to test all the code with the entry-level professional edition.

Download the example code files

You can download the example code files for this book from your account at www.packtpub.com. If you purchased this book elsewhere, you can visit www.packtpub.com/support and register to have the files emailed directly to you.

You can download the code files by following these steps:

Log in or register at www.packtpub.com.

Select the SUPPORT tab.

Click on Code Downloads & Errata.

Enter the name of the book in the Search box and follow the onscreen instructions.

Once the file is downloaded, please make sure that you unzip or extract the folder using the latest version of:

WinRAR/7-Zip for Windows

Zipeg/iZip/UnRarX for Mac

7-Zip/PeaZip for Linux

The code bundle for the book is also hosted on GitHub at https://github.com/PacktPublishing/Delphi-High-Performance/. In case there's an update to the code, it will be updated on the existing GitHub repository.

We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing/. Check them out!

Conventions used

There are a number of text conventions used throughout this book.

CodeInText: Indicates code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles. Here is an example: "A string parameter value is present in a string list."

A block of code is set as follows:

function IsPresentInList(strings: TStrings; const value: string): Boolean;


var


i: Integer;


begin


Result := False;


for i := 0 to strings.Count - 1 do


if SameText(strings[i], value) then


Exit(True);


end;

Bold: Indicates a new term, an important word, or words that you see onscreen. For example, words in menus or dialog boxes appear in the text like this. Here is an example: "Go to Options | Options, then select General | Search directory."

Warnings or important notes appear like this.

Tips and tricks appear like this.

Get in touch

Feedback from our readers is always welcome.

General feedback: Email feedback@packtpub.com and mention the book title in the subject of your message. If you have questions about any aspect of this book, please email us at questions@packtpub.com.

Errata: Although we have taken every care to ensure the accuracy of our content, mistakes do happen. If you have found a mistake in this book, we would be grateful if you would report this to us. Please visit www.packtpub.com/submit-errata, selecting your book, clicking on the Errata Submission Form link, and entering the details.

Piracy: If you come across any illegal copies of our works in any form on the Internet, we would be grateful if you would provide us with the location address or website name. Please contact us at copyright@packtpub.com with a link to the material.

If you are interested in becoming an author: If there is a topic that you have expertise in and you are interested in either writing or contributing to a book, please visit authors.packtpub.com.

Reviews

Please leave a review. Once you have read and used this book, why not leave a review on the site that you purchased it from? Potential readers can then see and use your unbiased opinion to make purchase decisions, we at Packt can understand what you think about our products, and our authors can see your feedback on their book. Thank you!

For more information about Packt, please visit packtpub.com.

Глава 1. О производительности

"My program is not fast enough. Users are saying that it is not performing well. What can I do?"

«Моя программа недостаточно быстра. Пользователи говорят, что она выполняется не очень хорошо. Что я могу сделать?»

These are the words I hear a lot when consulting on different programming projects. Sometimes the answer is simple, sometimes hard, but almost always the critical part of the answer lies in the question. More specifically, in one word - performing.

Эти слова я часто слышу, консультируя по различным проектам программирования. Иногда ответ прост, иногда труден, но почти всегда решающая часть ответа заключается в вопросе. Точнее, одним словом — выполнение.

What do we mean when we say that a program is performing well? Actually, nobody cares. What we have to know is what users mean when they say that the program is not performing well. And users, you'll probably admit, look at the world in a very different way than we programmers.

Что мы имеем в виду, когда говорим, что программа выполняется хорошо? На самом деле, это никого не волнует. Что мы должны знать, так это то, что пользователи имеют в виду, когда говорят, что программа выполняется плохо. И пользователи, вы, вероятно, согласитесь, смотрят на мир совсем по-другому, чем мы, программисты.

Before starting to measure and improve the performance of a program, we have to find out what users really mean by the word performance. Only then can we do something productive about it.

Прежде чем начать измерять и улучшать производительность программы, мы должны выяснить, что пользователи на самом деле подразумевают под словом «производительность». Только тогда мы сможем сделать с этим что-то продуктивное.

We will cover the following topics in this chapter:

В этой главе мы рассмотрим следующие темы:

What is performance?

Что такое производительность?

What do we mean when we say that a program performs well?

Что мы имеем в виду, когда говорим, что программа выполняется хорошо?

What can we tell about the code speed by looking at the algorithm?

Что мы можем сказать о скорости кода, посмотрев на алгоритм?

How does the knowledge of compiler internals help us write fast programs?

Как знание внутренних компонентов компилятора помогает нам писать быстрые программы?

Why is it better to measure than to guess?

Почему лучше измерить, чем угадать?

What tools can we use to find the slow parts of a program?

Какие инструменты мы можем использовать для поиска медленных частей программы?

Что такое производительность?

To better understand what we mean when we say that a program is performing well, let's take a look at a user story. In this book, we will use a fictitious person, namely Mr. Smith, Chief of Antarctica Department of Forestry. Mr. Smith is stationed in McMurdo Base, Antarctica, and he doesn't have much real work to do. He has already mapped all the forests in the vicinity of the station and half of the year it is too dark to be walking around and counting trees, anyway. That's why he spends most of his time behind a computer. And that's also why he is very grumpy when his programs are not performing well.

Чтобы лучше понять, что мы имеем в виду, когда говорим, что программа выполняется хорошо, давайте взглянем на историю пользователей. В этой книге мы будем использовать вымышленного человека, а именно мистера Смита, начальника Департамента лесного хозяйства Антарктиды. Мистер Смит находится на базе Макмердо, Антарктида, и у него не так много реальной работы. Он уже нанес на карту все леса в окрестностях станции, и в любом случае полгода слишком темно, чтобы ходить и считать деревья. Вот почему он проводит большую часть своего времени за компьютером. И именно поэтому он очень сердит, когда его программы не выполняется хорошо.

Some days he writes long documents analyzing the state of forests in Antarctica. When he is doing that, he wants the document editor to perform well. By that he actually means that the editor should work fast enough so that he doesn't feel any delay (or lag, as we call the delay when dealing with user input) while typing, preparing graphs, formatting tables, and so on.

Несколько дней он пишет длинные документы, анализирующие состояние лесов в Антарктиде. Когда он это делает, он хочет, чтобы редактор документов выполнялся хорошо. Под этим он фактически подразумевает, что редактор должен выполняться достаточно быстро, чтобы он не чувствовал никакой задержки (или запаздывания, как мы называем задержку при работе с пользовательским вводом) при вводе текста, подготовке графиков, форматировании таблиц и так далее.

In this scenario, performance simply means working fast enough and nothing else. If we speed up the operation of the document editor by a factor of two, or even by a factor of ten, that would make no noticeable improvement for our Mr. Smith. The document editor would simply stay fast enough as far as he is concerned.

В этом сценарии производительность просто означает достаточно быструю работу и ничего больше. Если мы ускорим работу редактора документов в два или даже в десять раз, это не принесет заметного улучшения нашему мистеру Смиту. Редактор документов просто оставался бы достаточно быстрым, насколько это имеет к нему отношение.

The situation completely changes when he is querying a large database of all of the forests on Earth and comparing the situation across the world to the local specifics of Antarctica. He doesn't like to wait and he wants each database query to complete in as short a time as possible. In this case, performance translates to speed. We will make Mr. Smith a happier person if we find a way to speed up his database searches by a factor a ten. Or even a factor of five; or two. He will be happy with any speedup and he'd praise us up to the heavens.

Ситуация полностью меняется, когда он запрашивает большую базу данных всех лесов на Земле и сравнивает ситуацию во всем мире с местными особенностями Антарктиды. Он не любит ждать и хочет, чтобы каждый запрос к базе данных выполнялся как можно быстрее. В этом случае производительность переводится в скорость. Мы сделаем мистера Смита более счастливым человеком, если найдем способ ускорить поиск в его базе данных в десять раз. Или даже в пять раз, или в два. Он будет рад любому ускорению и вознесет нас до небес.

After all this hard work, Mr. Smith likes to play a game. While the computer is thinking about a next move, a video call comes in. Mr. Smith knows he's in for a long chat and he starts resizing the game window so that it will share the screen with a video call application. But the game is thinking hard and is not processing user input and poor Mr. Smith is unable to resize it, which makes him unhappy.

После всей этой тяжелой работы мистер Смит любит поиграть в игру. Пока компьютер обдумывает следующий шаг, поступает видеовызов. Мистер Смит знает, что ему предстоит долгий чат, и он начинает изменять размер окна игры так, чтобы оно делило экран с приложением для видеовызовов. Но игра напряженно думает и не обрабатывает пользовательский ввод, и бедный мистер Смит не может изменить ее размер, что делает его несчастным.

In this example, Mr. Smith simply expects that the application's user interface will respond to his commands. He doesn't care if the application takes some time to find the next move, as long as he can do with the application what he wants to. In other words, he wants a user interface that doesn't block.

В этом примере мистер Смит просто ожидает, что пользовательский интерфейс приложения будет реагировать на его команды. Ему все равно, потребуется ли приложению какое-то время, чтобы найти следующий ход, пока он может делать с приложением то, что хочет. Другими словами, ему нужен пользовательский интерфейс, который не блокируется.

Различные типы скорости

It is obvious from the previous example that we don't always mean the same thing when we talk about a program's speed. There is a real speed, as in the database example, and there is a perceived speed, hinted at in the document editor and game scenario. Sometimes we don't need to improve the program speed at all. We just have to make it not stutter while working (by making the user interface responsive at all times) and users will be happy.

Из предыдущего примера очевидно, что мы не всегда имеем в виду одно и то же, когда говорим о скорости программы. Существует реальная скорость, как в примере с базой данных, и существует воспринимаемая скорость, на которую намекают редактор документов и сценарий игры. Иногда нам вообще не нужно повышать скорость работы программы. Нам просто нужно сделать так, чтобы она не запиналась во время работы (делая пользовательский интерфейс чувствительным все время), и пользователи будут счастливы.

We will deal with two types of performance in this book:

В этой книге мы рассмотрим два типа производительности:

Programs that react quickly to user input

Программы, которые быстро реагируют на ввод данных пользователем

Programs that perform computations quickly

Программы, которые быстро выполняют вычисления

As you'll see, the techniques to achieve the former and the latter are somehow different. To make a program react quickly, we can sometimes just put a long operation (as was the calculation of the next move in the fictitious game) into a background thread. The code will still run as long as in the original version but the user interface won't be blocked and everybody will be happy.

Как вы увидите, методы достижения первого и второго в чем-то отличаются. Чтобы заставить программу быстро реагировать, мы иногда можем просто поместить длительную операцию (как это было при расчете следующего хода в вымышленной игре) в фоновый поток. Код будет работать так же долго, как и в оригинальной версии, но пользовательский интерфейс не будет заблокирован, и все будут довольны.

To speed up a program (which can also help with a slowly-reacting user interface), we can use different techniques, from changing the algorithm to changing the code so that it will use more than one CPU at once to using a hand-optimized version, either written by us or imported from an external library.

Чтобы ускорить программу (что также может помочь с медленно реагирующим пользовательским интерфейсом), мы можем использовать различные методы, от изменения алгоритма до изменения кода, чтобы он использовал более одного процессора одновременно, до использования оптимизированной вручную версии, написанной нами или импортированной из внешней библиотеки.

To do anything, we have to know which part of the code is causing a problem. If we are dealing with a big legacy program, problematic part may be hard to find. In the rest of this chapter, we will look at different ways to locate such code. We'll start by taking an educated guess and then we'll improve that by measuring the code speed, first by using home-grown tools and then with a few different open source and commercial programs.

Чтобы что-то сделать, мы должны знать, какая часть кода вызывает проблему. Если мы имеем дело с большой устаревшей программой, проблемную часть может быть трудно найти. В остальной части этой главы мы рассмотрим различные способы поиска такого кода. Мы начнем с обоснованного предположения, а затем улучшим его, измерив скорость кода, сначала с помощью поставляемых инструментов, а затем с помощью нескольких различных программ с открытым исходным кодом и коммерческих программ.

Сложность алгоритма

Before we start with the dirty (and fun) job of improving program speed, I'd like to present a bit of computer science theory, namely the Big O notation.

Прежде чем мы начнем с грязной (и веселой) работы по повышению скорости работы программ, я хотел бы представить немного теории компьютерных наук, а именно нотацию Big O.

You don't have to worry, I will not use pages of mathematical formulas and talk about infinitesimal asymptotics. Instead, I will just present the essence of the Big O notation, the parts that are important to every programmer.

Вам не нужно беспокоиться, я не буду использовать страницы математических формул и говорить о бесконечно малой асимптотике. Вместо этого я просто изложу суть нотации Big O, те части, которые важны для каждого программиста.

In the literature and, of course, on the web, you will see expressions such as O(n), O(n^2), O(1) and similar. This fancy-looking notation hides a really simple story. It tells us how much slower the algorithm will become if we increase the data size by a factor of n.

В литературе и, конечно же, в сети вы увидите такие выражения, как O(n), O(n^2), O(1) и аналогичные. За этими причудливыми обозначениями скрывается действительно простая история. Это говорит нам о том, насколько медленнее станет алгоритм, если мы увеличим размер данных в n раз.

The n^2 notation means "n to the power of two", or n2. This notation is frequently used on the internet because it can be written with the standard ASCII characters. This book uses the more readable variant O(n2).

Обозначение n^2 означает «n в степени два», или n2. Это обозначение часто используется в Интернете, потому что она может быть написана стандартными символами ASCII. В этой книге используется более читаемый вариант O(n2).

Let's say we have an algorithm with complexity of O(n), which on average takes T seconds to process input data of size N. If we increase the size of the data by a factor of 10 (to 10*N), then the algorithm will (on average) also use 10 times more time (that is, 10*T) to process the data. If we process 1,000 times more data, the program will also run 1,000 times slower.

Допустим, у нас есть алгоритм со сложностью O(n), который в среднем занимает T секунд для обработки входных данных размера N. Если мы увеличим размер данных в 10 раз (до 10*N), то алгоритм (в среднем) также будет использовать в 10 раз больше времени (то есть 10*T) для обработки данных. Если мы обработаем в 1000 раз больше данных, программа также будет работать в 1000 раз медленнее.

If the algorithm complexity is O(n2), increasing the size of the data by a factor of 10 will cause the algorithm to run 102 or 100 times longer. If we want to process 1,000 times more data, then the algorithm will take 1,0002 or a million times longer, which is quite a hit. Such algorithms are typically not very useful if we have to process large amounts of data.

Если сложность алгоритма равна O(n2), увеличение размера данных в 10 раз приведет к тому, что алгоритм будет работать в 102 или 100 раз дольше. Если мы хотим обработать в 1 000 раз больше данных, то алгоритм займет в 1 0002 или в миллион раз больше времени, что является настоящим ударом. Такие алгоритмы, как правило, не очень полезны, если нам приходится обрабатывать большие объемы данных.

Most of the time, we use the Big O notation to describe how the computation time relates to the input data size. When this is the case, we call the Big O notation time complexity. Nevertheless, sometimes the same notation is used to describe how much storage (memory) the algorithm is using. In that case, we are talking about a space complexity.

Большую часть времени мы используем обозначение Big O, чтобы описать, как время вычисления связано с размером входных данных. Когда это так, мы называем нотацию Big O временно́й сложностью. Тем не менее, иногда та же нотация используется для описания объема хранилища (памяти), используемого алгоритмом. В этом случае мы говорим о пространственной сложности.

You may have noticed that I was using the word average a lot in the last few paragraphs. When talking about the algorithm complexity, we are mostly interested in the average behavior, but sometimes we will also need to know about the worst behavior. We rarely talk about best behavior because users don't really care much if the program is sometimes faster than average.

Возможно, вы заметили, что в последних нескольких абзацах я часто использовал слово «средний». Когда мы говорим о сложности алгоритма, нас в основном интересует среднее поведение, но иногда нам также нужно будет знать о наихудшем поведении. Мы редко говорим о лучшем поведении, потому что пользователям на самом деле все равно, если программа иногда работает быстрее, чем в среднем.

Let's look at an example. The following function checks whether a string parameter value is present in a string list:

Давайте рассмотрим пример. Следующая функция проверяет, присутствует ли значение строкового параметра в списке строк:

function IsPresentInList(strings: TStrings; const value: string): Boolean;

var

   i: Integer;

begin

   Result := False;

   for i := 0 to strings.Count - 1 do

      if SameText(strings[i], value) then

         Exit(True);

end;

What can we tell about this function? The best case is really simple—it will find that the value is equal to strings[0] and it will exit. Great! The best behavior for our function is O(1). That, sadly, doesn't tell us much as that won't happen frequently in practice.

Что мы можем сказать об этой функции? В лучшем случае все действительно просто — она обнаружит, что значение равно strings[0], и завершит работу. Отлично! Наилучшее поведение для нашей функции — O(1). Это, к сожалению, не говорит нам о многом, так как на практике такое случается нечасто.

The worst behavior is also easy to find. If the value is not present in the list, the code will have to scan all of the strings list before deciding that it should return False. In other words, the worst behavior is O(n), if the n represents the number of elements in the list. Incidentally (and without proof), the average behavior for this kind of search is also O(n).

Худшее поведение также легко найти. Если value отсутствует в списке, код должен будет просканировать весь список строк, прежде чем решить, что он должен вернуть значение False. Другими словами, наихудшее поведение — O(n), если n представляет количество элементов в списке. Кстати (и без доказательств), среднее поведение для такого рода поиска также равно O(n).

The Big O limits don't care about constant factors. If an algorithm would use n/2 steps on average, or even just 0.0001 * n steps, we would still write this down as O(n). Of course, a O(10 * n) algorithm is slower than a O(n) algorithm and that is absolutely important when we fine-tune the code, but no constant factor C will make O(C * n) faster than O(log n) if n gets sufficiently large.

Пределы Big O не заботятся о постоянных факторах. Если бы алгоритм использовал в среднем n/2 шага или даже всего 0,0001 * n шагов, мы бы все равно записали это как O(n). Конечно, алгоритм O(10 * n) работает медленнее, чем алгоритм O(n), и это абсолютно важно при точной настройке кода, но никакой постоянный коэффициент C не сделает O(C * n) быстрее, чем O(log n), если n станет достаточно большим.


There are better ways to check whether an element is present in some data than searching the list sequentially. We will explore one of them in the next section, Big O and Delphi data structures.

Есть лучшие способы проверить, присутствует ли элемент в некоторых данных, чем последовательный поиск по списку. Мы рассмотрим один из них в следующем разделе, Big O и структуры данных Delphi.

While the function of n inside the O() notation can be anything, there are some O functions that appear constantly in standard programming problems. The following table shows those Big O limits and the most common examples of problems that belong to each class:

В то время как функция n внутри обозначения O() может быть чем угодно, есть некоторые функции O, которые постоянно появляются в стандартных задачах программирования. В следующей таблице показаны эти пределы Big O и наиболее распространенные примеры задач, относящихся к каждому классу:


Временна́я сложность Общие примеры проблем с такой временно́й сложностью
O(1) Доступ к элементам массива
O(log n) Поиск в упорядоченном списке
O(n) Линейный поиск
O(n log n) Быстрая сортировка (среднее поведение)
O(n2) Быстрая сортировка (худшее поведение), простая сортировка (пузырьковая сортировка, сортировка вставкой, сортировка выбором)
O(cn) Рекурсивная задача Фибоначчи, задача коммивояжера с использованием динамического программирования (c-некоторая числовая константа)

If we care about program performance, then O(1) algorithms are of special interest to us as they present algorithms which don't get slower (at least not noticeably) when we increase the problem size. We'll see an example of such O(1) algorithms in the next section.

Если мы заботимся о производительности программы, то алгоритмы O(1) представляют для нас особый интерес, поскольку они представляют алгоритмы, которые не замедляются (по крайней мере, не заметно), когда мы увеличиваем размер проблемы. Пример таких алгоритмов O(1) мы рассмотрим в следующем разделе.

When we deal with algorithms that search in some datasets, we usually try to make them behave as O(log n), not O(n), as the former slows down much, much slower than the latter.

Когда мы имеем дело с алгоритмами, которые выполняют поиск в некоторых наборах данных, мы обычно пытаемся заставить их вести себя как O(log n), а не O(n), так как первый замедляется намного, намного медленнее, чем второй.

Another big class of problems deals with sorting the data. While the naive approaches sort in O(n2), better algorithms (such as mergesort and quicksort) need on average just O(n log n) steps.

Еще один большой класс проблем связан с сортировкой данных. В то время как простые подходы сортируются по O(n2), лучшим алгоритмам (такие как сортировка слиянием и быстрая сортировка) требуется в среднем всего O(n log n) шагов.

The following image shows how the time complexity for these typical limits (we have used 2n as an example of a more generic cn) grows when we increase the problem size up to 20-fold:

На следующем рисунке показано, как возрастает временная сложность для этих типичных пределов (мы использовали 2n в качестве примера более общего cn), когда мы увеличиваем размер задачи до 20 раз:


Наиболее часто встречающиеся пределы Big O

We can see that O(1) and O(log n) grow very slowly. While O(n log n) grows faster than O(n), it also grows much slower than O(n2), which we had to stop plotting when data was increased nine-fold.

Мы видим, что O(1) и O(log n) растут очень медленно. В то время как O(n log n) растет быстрее, чем O(n), он также растет намного медленнее, чем O(n2), так что нам пришлось прекратить строить график, когда данные были увеличены в девять раз.

The O(2n) starts slowly and looks like a great solution for small data sizes (small n), but then it starts rising terribly fast, much faster than O(n2).

O(2n) начинается медленно и выглядит как отличное решение для небольших размеров данных (небольшое n), но затем он начинает расти ужасно быстро, намного быстрее, чем O(n2).

The following table shows how fast O(n log n) and O(n2) are growing if we compare them with O(n) and how quickly O(2n) explodes.

В следующей таблице показано, как быстро растут O(n log n) и O(n2), если мы сравним их с O(n), и как быстро взрывается O(2n).

The data column shows the data size increase factor. The number 10 in this column, for example, represents input with 10 times more elements than in the original data:

В столбце «Размер данных» показан коэффициент увеличения размера данных. Число 10 в этом столбце, например, представляет входные данные с в 10 раз большим количеством элементов, чем в исходных данных:


Размер данных O(1) O(log n) O(n) O(n log n) O(n2) O(2n)
1 1 1 1 1 1 1
2 1 2 2 4 4 2
10 1 4 10 43 100 512
20 1 5 20 106 400 524 288
100 1 8 100 764 10 000 1029
300 1 9 300 2,769 90 000 1090

We can see from this table that O(log n) algorithms present a big improvement over O(n) algorithms (8 versus 100 times increase in time when data increases 100-fold). We can also see that the O(2n) quickly becomes completely unmanageable.

Из этой таблицы мы видим, что алгоритмы O(log n) представляют собой значительное улучшение по сравнению с алгоритмами O(n) (в 8 раз по сравнению со 100-кратным увеличением времени, когда данные увеличиваются в 100 раз). Мы также можем видеть, что O(2n) быстро становится совершенно неуправляемым.

The last cell in this table is particularly interesting. There are different estimates for the number of elementary particles (electrons, protons, neutrons, and so on) in the visible universe, but they all lie somewhere around 1090. Suppose we have a computer which can solve an O(2n) in a reasonable time. If we would increase the input data by a factor of just 300, then we would need 1090 computers to solve the new problem in the same time. That is as much as the number of particles in the visible universe!

Последняя ячейка в этой таблице особенно интересна. Существуют различные оценки количества элементарных частиц (электронов, протонов, нейтронов и так далее) в видимой Вселенной, но все они лежат где-то около 1090. Предположим, у нас есть компьютер, который может решить задачу O(2n) за разумное время. Если бы мы увеличили входные данные всего в 300 раз, то нам понадобилось бы 1090 компьютеров для решения новой проблемы за одно и то же время. Это столько же, сколько частиц в видимой Вселенной!

Don't use algorithms which have time complexity O(2n). It won't end well.

Не используйте алгоритмы, которые имеют временную сложность O(2n). Это добром не кончится.

Big O и структуры данных Delphi

Delphi's Run-Time Library (RTL) contains many data structures (classes that are specifically designed to store and retrieve data), mostly stored in System.Classes and System.Generics.Collection units that greatly simplify everyday work. We should, however, be aware of their good and bad sides.

Библиотека времени выполнения Delphi (RTL) содержит множество структур данных (классов, специально предназначенных для хранения и извлечения данных), в основном хранящихся в модулях System.Classes и System.Generics.Collection, которые значительно упрощают повседневную работу. Однако мы должны знать их хорошие и плохие стороны.

Every data structure in the world is seeking a balance between four different types of data access: accessing the data, inserting the data, searching for data, and deleting data. Some data structures are good in some areas, others in different ones, but no data structure in this world can make all four operations independent of data size.

Каждая структура данных в мире стремится к балансу между четырьмя различными типами доступа к данным: получение доступа к данным, вставка данных, поиск данных и удаление данных. Некоторые структуры данных хороши в одних областях, другие — в других, но никакая структура данных в этом мире не может сделать все четыре операции независимыми от размера данных.

When designing a program, we should therefore know what our needs are. That will help us select the appropriate data structure for the job.

Поэтому при разработке программы мы должны знать, каковы наши потребности. Это поможет нам выбрать подходящую структуру данных для работы.

The most popular data structure in Delphi is undoubtedly TStringList. It can store a large amount of strings and assign an object to each of them. It can—and this is important—work in two modes, unsorted and sorted. The former, which is a default, keeps strings in the same order as they were added while the latter keeps them alphabetically ordered.

Самой популярной структурой данных в Delphi, несомненно, является TStringList. Он может хранить большое количество строк и присваивать каждому из них объект. Он может — и это важно — работать в двух режимах: неотсортированном и отсортированном. Первый, который используется по умолчанию, сохраняет строки в том же порядке, в котором они были добавлены, в то время как второй сохраняет их в алфавитном порядке.

This directly affects the speed of some operations. While accessing any element in a string list can always be done in a constant time (O(1)), adding to a list can take O(1) when the list is not sorted and O(log n) when the list is sorted.

Это напрямую влияет на скорость выполнения некоторых операций. Хотя доступ к любому элементу в строковом списке всегда можно выполнить за постоянное время (O(1)), добавление в список может занять O(1), когда список не отсортирован, и O(log n), когда список отсортирован.

Why that big difference? When the list is unsorted, Add just adds a string at its end. If the list is, however, sorted, Add must first find a correct insertion place. It does this by executing a bisection search, which needs O(log n) steps to find the correct place.

Почему такая большая разница? Когда список не отсортирован, Add просто добавляет строку в его конец. Однако, если список отсортирован, сначала Add должен найти правильное место вставки. Он делает это, выполняя поиск половинным делением, для которого требуется O(log n) шагов, чтобы найти правильное место.

The reverse holds true for searching in a string list. If it is not sorted, IndexOf needs to search (potentially) the whole list to find an element. In a sorted list, it can do it much faster (again by using a bisection) in O(log n) steps.

Обратное справедливо для поиска в списке строк. Если он не отсортирован, IndexOf необходимо выполнить поиск (потенциально) по всему списку, чтобы найти элемент. В отсортированном списке это может быть сделано намного быстрее (опять же, с помощью половинного деления) за O(log n) шагов.

We can see that TStringList offers us two options - either a fast addition of elements or a fast lookup, but not both. In a practical situation, we must look at our algorithm and think wisely about what we really need and what will behave better. ...



Все права на текст принадлежат автору: Примож Габриэльчич.
Это короткий фрагмент для ознакомления с книгой.
Высокая производительность Delphi (черновик перевода главы 1)Примож Габриэльчич