Unbelievable performance gain by changing an Algorithm

Visual Foxpro added Object Oriented Programming in version 3 which was released about 10 years ago. Back then users weren’t expected to use very many objects. Nowadays, with more memory, users create thousands of objects, and things were slowing down.

OOP means that the user can create an object then send it commands by calling methods and inspecting properties of the objects.

It’s very much taken for granted today, but it’s an extremely powerful capability. It’s much more than Object Based programming, which VB 6, Excel, and COM allow.

Type this in the Fox command window:

oExcel=CREATEOBJECT("excel.application")

oExcel.

An instance of Excel is created. When you type the “.”, intellisense shows the methods and properties of the Excel Application object.

So you can create an excel worksheet and manipulate it very easily:

oExcel=CREATEOBJECT("excel.application")

oExcel.Visible=1

oExcel.Workbooks.Add

oExcel.Cells(1,1).Value="Hi There"

This is object based programming: which doesn’t have inheritance, a key ingredient to Object Oriented Programming.

With inheritance, the user can create an object Class which can inherit properties of another class.

For example, an accounting application might have many forms, each of which might have a class with labels and textboxes for Name, Address, City, State Zip.

The user could create a visual class called “MyAddressClass” A visual class is one that can be designed in the Visual Class designer, which is very similar to the form designer. The user can specify controls and sizes, fonts and labels in the designer.

Perhaps on some forms, the Address Class might have additional fields, like phone number or email. Another class “MyAddressClassWithPhone” can be created that inherits from “MyAddressClass”

When the user wants to change the Address line to have a bold font, then the appropriate modification to the “MyAddressClass” will automatically be inherited by all other child classes.

Internally, the VFP objects were maintained as a linked list of structures. There was a pointer to the linked list root which pointed to the first object. Each object structure had a pointer to the next. This worked fine for small numbers of objects, but when there are thousands, the time to traverse the linked list became significant. In algorithm speak, it’s O(n^2) (order n^2: for 1000 objects, 1,000,000 operations).

For VFP8, I changed the way objects were stored from a linked list to a table. That meant instant access to any object within the table, so traversing all the objects was O(n) (linear: for 1000 objects, 1000 operations). Some operations became constant in time, regardless of the number of objects.

This fundamental algorithm change made huge gains in performance, which some people said were “unbelievable”

Creating 1000 objects went from 25 seconds to less than half a second.

45233