Help me make this code faster!

#1

Hi, I have a Java assignment. The code I currently have is too slow and I need to implement a faster solution.

The code:

[code=java] if (readqueue_size > 0) {

        int lastReadTrack = DiskSim.block_to_track(blk);

        /*
         * The distance is set to max_value for the first iteration to
         * complete, to ensure the first blk is not the closest
         */
        int distance = Integer.MAX_VALUE;
        int closestDistance = 0;

        for (int i = readqueue_tail; i < readqueue_head; i++) {
            int val = lastReadTrack - DiskSim.block_to_track(readqueue[i].blk);
            closestDistance = (val < 0) ? -val : val;

            while (distance > closestDistance) {
                distance = closestDistance;

                int prevTailBlock = readqueue[readqueue_tail].blk;
                BRequest prevTailReq = readqueue[readqueue_tail].req;

                readqueue[readqueue_tail].blk = readqueue[i].blk;
                readqueue[readqueue_tail].req = readqueue[i].req;

                readqueue[i].blk = prevTailBlock;
                readqueue[i].req = prevTailReq;
            }
        }[/code]

I need to rewrite it, so it’s faster. Anybody know what I could do?

#2

closestDistance = (val < 0) ? -val : val;

Math.abs?

#3

[quote=“Pwnd, post:2, topic:555208”]closestDistance = (val < 0) ? -val : val;

Math.abs?[/quote]

I’m not allowed to use any Java classes or foreach loops. Forgot to mention that, sorry.
Integer.MAX_VALUE, I can’t even use that. That will be changed soon.

#4

This is why Java isn’t used for things like (what I assume to be a simulation of) native disk IO – it’s just too slow. We can start with some obvious optimizations though.

Branching is slow and bit manipulation is fast, so let’s do that for abs (see here how it works):

It could probably be simplified further but the point is to remove the branching.

Why are you using a while loop? You check to see if distance is strictly greater than closestDistance, if it is, you assign the former to the latter, then the loop’s condition will always be false since distance == closestDistance and they will remain constant in the loop body.

You should cache your reads from readqueue[...].

[hr]

The best optimizations will be from refactoring the algorithm itself, not from those small optimizations, which is hard to do with such a small and incomplete code sample. Are you sure this is where the bottleneck is? What about DiskSim.block_to_track? Objects in Java are not just structs with some pointers; there’s lots involved in calling methods. Might be worth using a tool to find some hot spots.

#5

Yeah, you’re right. It is a sim of naive disk IO and the assignment is for disk scheduling. Java and erlang are the only programming languages that we learn in the core modules however we have special classes for C, C++, etc. Classes such as DiskSim and all the arrays available are provided. I’d give you the whole source code but it would be pointless (imo).

Here’s the complete method:

public void readcomplete(int blk, BRequest req) {
        if (blk >= 0) {
            /* give the block read back to the high-level system */
            DiskSim.highlevel_didread(blk, req);
        }

        if (readqueue_size > 0) {

            int lastReadTrack = DiskSim.block_to_track(blk);

            /*
             * The distance is set to max_value for the first iteration to
             * complete, to ensure the first blk is not the closest
             */
            int distance = Integer.MAX_VALUE;
            int closestDistance = 0;

            for (int i = readqueue_tail; i < readqueue_head; i++) {
                int val = lastReadTrack - DiskSim.block_to_track(readqueue[i].blk);
                closestDistance = (val < 0) ? -val : val;

                while (distance > closestDistance) {
                    distance = closestDistance;

                    int prevTailBlock = readqueue[readqueue_tail].blk;
                    BRequest prevTailReq = readqueue[readqueue_tail].req;

                    readqueue[readqueue_tail].blk = readqueue[i].blk;
                    readqueue[readqueue_tail].req = readqueue[i].req;

                    readqueue[i].blk = prevTailBlock;
                    readqueue[i].req = prevTailReq;
                }
            }

            /*
             * still got requests to service, dispatch the next block request
             * (at tail)
             */
            DiskSim.disk_readblock(readqueue[readqueue_tail].blk, readqueue[readqueue_tail].req);

            /* increment tail pointer, modulo buffer size */
            readqueue_tail = (readqueue_tail + 1) % DiskSim.MAXREQUESTS;
            readqueue_size--;
        }
    }

The code I posted on thread was what I added. The assignments task is to modify readcomplete method only. What I had to do was implement a disk scheduling algo. E.g. SSTF, Scan, C-Scan or whatever I can find/create that is better. When running the application you get a type of score to see how well your implentation performed. So far I’m getting 700-1000 which is good but not A grade. I need the score to be 500-600 or less.

“If there are errors in your code that cause incorrect blocks to be read, the simulation framework will emit various errors as it runs. These generally indicate serious problems with your scheduling algorithm — i.e. it is reading or returning the wrong blocks.” So far that code I showed was my implementation of SSTF.

Regards to the Math.abs justaguy, thank you for that. Very helpful. The while loop was a meh, blame my lack of understanding.

Thanks for the comments.

#6

It sounds like you’re being scored on the number of DiskSim calls you have to make? So you need to reduce that number by using a better scheduling algorithm, not optimising bits of slow java. What scores do you get with the different types of algorithm?

#7

Lol yes, this is the fastest I’m getting. Everything else I’ve tried is slower then 700 and google shows that SSTF is the fastest. My lecturer said that if it’s too slow find another algo or do something myself to make it faster.