Register
View RSS Feed

//no comment

Scanning Even Faster

Rate this Entry
First of all, I've talked about how extremely optimized TSM's scans already are in the past. I have no doubt that, when compared apples to apples, TSM's scan speed blows any other addon out of the water as it stands today. Comparing TSM to other addons is not the purpose of this blog post, just know that there are already a ton of optimizations in place in TSM's scanning code as I've previously described.

At the end of the day, scanning fast comes down to scanning less pages. Nearly all of the time spent scanning is simply waiting for Blizzard to provide the data to the client. Lately, loading a single page is taking on average 2-3 seconds (it was around 1 second before WoD). Every page which can be avoided completely is a huge speed-up. TSM already "skips" entire pages by using combined searches to fit more auctions onto each page which is scanned.

One common issue which was made worse now that the auction houses are merged is people who post hundreds of singles of an item. This caused the total number of pages TSM had to scan to grow tremendously. This got me thinking about how TSM could be taught to detect that somebody has posted a lot of singles and try and skip scanning every page of their singles without missing any auctions. Because of how the auction house is scanned, if auction X is a specific item/stackSize/seller/bid/buyout and auction Y is the same item/stackSize/seller/bid/buyout, we can know for certain that every auction in between must also be the same as X and Y without needing to scan them. Skipping a few auctions within a single page doesn't save us noticeable amount of time, but if we can use this technique to skip entire pages, that would be significant.

The basic idea is to scan page 1 and then instead of moving on to page 2, skip ahead to page 3. If the first auction of page 3 is identical to the last auction of page 1, then everything on page 2 must also be identical and we've skipped an entire page. Otherwise, we just go back and scan page 2 and are no worse-off than we would have been if we went in order. The actual implementation is a bit more complex (it attempts to skip multiple pages in multiple steps), but at worst it scans every page exactly once, just as it did previously. In my testing, I was seeing scans where >30% of the pages were being skipped entirely for high-quantity items which is a significant time-saver.


There's one other scan-speed improvement which I've been working on this weekend. When you are buying auctions with TSM_Shopping, it must navigate to the page with the auction you want to buy before you can buy it. This searching is currently fairly dumb. Most of the time It just scans every page, in order, until it finds the auction it's looking for. If it's a 200 stack of ore that it's looking for, this could mean an extra 20 seconds of scanning. The new method is much faster. When the auctions are initially scanned (i.e. when you hit the search button) they will now be stored in a temporary database. This database will be maintained to accurately mirror what is on the AH (in the same order). This means that TSM_Shopping can just find the position of an auction within the database, determine exactly which page on the AH it will be on, and go directly to that page.

The only problem is that the AH may have changed since you ran the scan and the database might not line up perfectly. However, the scanning code will still try the page which the database tells it to try first. In the best case, the auction is still on that page and we only had to scan 1 page to find it. If it's not on that page, the code will figure out whether it will be on a higher or lower page (based on sorting of AH), and start scanning either up or down from the initial page it tried. It's very likely that the auction it's looking for is within 1 or 2 pages of where it starts, so it'll almost always find the auction in 1 or 2 pages. This is MUCH better than the 10+ pages from the old method.


These enhancements are not currently in the addon, and are targeted for TSM3. So, don't expect your scan speeds to go up tomorrow, but know that there's a lot of good stuff coming!

Comments

  1. Sterling's Avatar
    That's brilliant Sapu. Scan speed improvements mean a LOT for users on high pop realms such as my own.

    Have you implemented other scan speed improvements lately? I've noticed shorter scan times in the past couple weeks. Might have been improvements on Blizzard's end though (or less players bogging down the AH).

    What kind of timeline are we looking at for TSM3, if any?
    Updated February 8th, 2015 at 01:39 PM by Sterling
  2. Sapu94's Avatar
    There haven't been any scan speed improvements made in TSM2. It's likely just that the number of players is decreasing as we get further into WoD.

    As far as the TSM3 timeline, there isn't really one, but I'm hoping to have a beta out relatively soon (1-2 months maybe). We started working on TSM3 in early September. Based on our prior track record with major releases, it takes about 9-12 months before it's actually released (including a few months of beta testing). Based on that, you could extrapolate that TSM3 will be released in the summer which is as good of a guess as anything.
    Updated February 8th, 2015 at 03:00 PM by Sapu94