Partager via

Unbelievable performance gain by changing an Algorithm

  • Article

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

Comments

  • Anonymous
    December 06, 2004
    Wow !! That Explains why the Earlier Software Runs Amazing Fast in VFP 8.0

    Thanks for the Insight , I thought the Credit went to P4 2.2 , 1 Gig RAM

  • Anonymous
    December 06, 2004
    Ok, I've never worked with FoxPro, but in your example I can only assume you are late-binding to the COM object you are requesting. That said, I am surprised that you get intellisense, as you don't in VB6, only with early binding is this available (for VB6 that is). I'm assuming that under the covers you using the IUnknown pointer to request an ITypeInfo pointer to display specific information to the user? If this is the case, which makes it much more helpful for the programmer that doesn't read documentation I wonder why this wasn't implemented in VB6?

  • Anonymous
    December 06, 2004
    Hi Calvin,

    Congratulations! This is the kind of blog entry we would expect from Microsoft people! Clear, Concise and highly explanatory.

    Great entry! Keep on the excellent work!

  • Anonymous
    December 07, 2004
    Fabio: Thanks for the feedback. Naturally, positive feedback will lead to more similar posts

    Nick: Great idea for a new blog: stay tuned.

    Kanchi: As always, improving performance means taking out the slow parts!

  • Anonymous
    December 15, 2004
    Yes, this was one that was greatly appreciated. There were techniques people used to not instantiate objects until truly needed in order to keep the code speedy. So not only did you increase the speed, but you let us get rid of unnecessary code, thereby lowering the chances of bugs and lowering the maintenance chore.

  • Anonymous
    December 15, 2004
    Thanks to Alex Feldstein pointing at this blog. Valuable info, good insight; for sure I will stay tuned. Clavin, thanks!

  • Anonymous
    January 16, 2009
    <a href= http://qvvqfvy.angelfire.com >wild violets in lawn</a> <a href= http://bhebave.angelfire.com >large acrylic poster holders</a> <a href= http://tavuaay.angelfire.com >caala</a> <a href= http://znioage.angelfire.com >s inn emporia virginia</a> <a href= http://njubada.angelfire.com >cheap skateboard com</a>

  • Anonymous
    January 22, 2009
    PingBack from http://www.hilpers.fr/831443-des-temps-de-reponses-enormes