Tuesday, November 11, 2014

PHP Search Speed

I recently had a problem with a PHP command line script I use to sanity check some of our systems.

One particular check compares user accounts across a number of systems. There are ~100,000 user accounts. The script loads data in to memory from various LDAP and SQL interfaces. Once in memory, it iterates through the records and compares them. This process takes a few minutes, mostly spent loading data via LDAP.

I had identified a data problem in one system which uses SQL to get the user data. The SQL in question already joins a few tables and rather than introduce another complex join, I decided to just load the data about the new item into a new array using a separate SQL statement. This added just a few seconds to the script run time. However, once I implemented the record compare, the speed of the script slowed to a halt.

This was unexpected because I regularly process data sets this size and larger in PHP without and problems (once I raise the memory_limit).

This is what I discovered while debugging this problem:
It is well known that the PHP in_array & array_search functions are slow. They perform a linear search on the array resulting in O(n) performance.
Many people have contributed code which can implement a binary search on an array. This in theory reduces the performance to O(log n). My testing shows an improvement in search times but they are still quite slow and not representitive of the perforamce I am use to.
So how was it that I have never had this problem before? A quick inspection of my existing code shows that I always retrieve data by using the key. This results in a hashtable lookup of O(1).
So I changed my code to store my new data in the array key and use isset($array[$key]) and bang! my script is running on time again.

Footnote:

The performance of these functions may not be exactly O(n), O(log n) and O(1) but are close enough to enable comparing the performance of these functions against each other.

9 comments:

  1. That’s a great news, every country should take steps like this. geometry dash

    ReplyDelete
  2. I feel it interesting, your post gave me a new perspective! I have read many other articles about the same topic, but your article convinced me! I hope you continue to have high quality articles like this to share with everyone!
    happy wheels

    ReplyDelete
  3. The article you have shared here very awesome. I really like and appreciated your work. I read deeply your article, the points you have mentioned in this article are useful
    vex 3

    ReplyDelete
  4. Text API integration plays a vital role in enabling your existing applications or systems to be mobile. When you integrate your software or application with a reliable and feature-rich text API, then delivering real-time communication to your customers is easy.

    ReplyDelete

  5. لذلك تحرص شركتنا ارخص شركة مكافحة حشرات بالرياض كأفضل الشركات الموجودة فى الرياض على التخلص من جميع الأفات الشرسه مثلا الفئران وغيرها من القوارض التى من الممكن ان تكون سبب فى تدمير اغراض اى منزل او قد تسبب بعض الامراض اونقلها.شركة مكافحة النمل الاسود بالرياض _ شركة مكافحة الصراصير بالرياض _ شركة مكافحة البق بالرياض _ شركة مكافحة الوزغ بالرياض _ شركة مكافحة الثعابين بالرياض

    ReplyDelete
  6. What a nice Images are there in it helix jump

    ReplyDelete
  7. It is a great article. You will surely like this also because it is a great stuff

    Raft Wars 2

    ReplyDelete
  8. Really informative article.Really looking forward to read more. Really Cool. คาสิโนออนไลน์ที่น่าเชื่อถือและมีความเป็นมืออาชีพที่สุดในตอนนี้
    โปรโมชั่นGclub ของทางทีมงานตอนนี้แจกฟรีโบนัส 50%
    เพียงแค่คุณสมัคร สล็อตออนไลน์ กับทางทีมงานของเราเพียงเท่านั้น
    ร่วมมาเป็นส่วนหนึ่งกับเว็บไซต์คาสิโนออนไลน์ของเราได้เลยค่ะ
    สมัครสล็อตออนไลน์ >>> Goldenslot
    สนใจร่วมสนุกกับ คาสิโนออนไลน์ คลิ๊กได้เลย
    มีทั้งคาสิโนออนไลน์ หวยออนไลน์ ฟุตบอลออนไลน์ สล็อตออนไลน์ และอื่นๆอีกมากมาย

    ReplyDelete