Optimize Your API Using Memoization

When an endpoint goes slow, I apply my framework of 4 steps.

First I add the memoization. If it’s not enough, I add pagination. If it’s not enough I denormalize some data in the database. And if it’s not enough I add a cache server.

You can see more details about all those steps in this article.

In the article of today, I will describe in detail the first step. The memoization.

What’s The Memoization?

The memoization is a process where I switch from using CPU resources to use Memory resources.

Let’s go directly with an example.

public List<VehicleDto> findVehicles(
      SearchCriteria searchCriteria) {
   List<VehicleDto> results = new ArrayList<>();

   List<Vehicle> vehicles = repository.findAll(searchCriteria);

   for (Vehicle vehicle : vehicles) {
      VehicleDto vehicleDto = mapper.toDto(vehicle);

      this.addImagesInfo(vehicleDto);

      this.addPriceInfo(vehicleDto);

      this.addLocationInfo(vehicleDto);
   }

   return results;
}

private void addImagesInfo(VehicleDto vehicle) {
   List<Image> images = repository.findImages(vehicle.getId());
   mapper.updateVehicleWithImages(vehicle, images);
}

private void addPriceInfo(VehicleDto vehicle) {
   Price price = repository.findPrice(vehicle.getId());
   mapper.updateVehicleWithPrice(vehicle, price);
}

private void addLocationInfo(VehicleDto vehicle) {
   Location location = repository.findLocation(vehicle.getId());
   mapper.updateVehicleWithLocation(vehicle, location);
}

The problem here is that I have several requests inside the for-loop.

The example was simplified, because this case could be solved with a better query to the database using joins. But what if each private method (addImagesInfo, addPriceInfo, addLocationInfo) has some complex logic that I can’t handle in the database?

Let’s start with the solution.

Reproduce It Locally

TThe first step is always trying to reproduce the request locally. This means:

Get the database data (or connect to an existing database);
Get the request to optimize;
Run locally to confirm it’s slow;
Make several tests to save the different execution times.

If I’m unable to reproduce the request locally, I can’t ensure my modifications improve the behavior.

I must start with a goal. If the request lasts 2 seconds at the beginning, I won’t stop until I’ve reached half the time.

Find the Slower Loops or Methods

Once I’m able to reproduce the problem locally, I can focus on where the time is consumed.

I have several tools that can do it for me. Like VisualVM or YourKit. But those are complex tools. And they have a very verbose output.

I have another easy way to do it. Just use logs.

public List<VehicleDto> findVehicles(
      SearchCriteria searchCriteria) {
   long start = System.currentTimeMillis();
   List<VehicleDto> results = new ArrayList<>();

   List<Vehicle> vehicles = repository.findAll(searchCriteria);

   log.info("find all vehicles took " + (System.currentTimeMillis() - start));
   start = System.currentTimeMillis();

   for (Vehicle vehicle : vehicles) {
      start = System.currentTimeMillis();
      VehicleDto vehicleDto = mapper.toDto(vehicle);

      log.info("map a single vehicle took " + (System.currentTimeMillis() - start));
      start = System.currentTimeMillis();

      this.addImagesInfo(vehicleDto);

      log.info("read images took " + (System.currentTimeMillis() - start));
      start = System.currentTimeMillis();

      this.addPriceInfo(vehicleDto);

      log.info("read price took " + (System.currentTimeMillis() - start));
      start = System.currentTimeMillis();

      this.addLocationInfo(vehicleDto);

      log.info("read location took " + (System.currentTimeMillis() - start));
   }

   return results;
}

private void addImagesInfo(VehicleDto vehicle) {
   List<Image> images = repository.findImages(vehicle.getId());
   mapper.updateVehicleWithImages(vehicle, images);
}

private void addPriceInfo(VehicleDto vehicle) {
   Price price = repository.findPrice(vehicle.getId());
   mapper.updateVehicleWithPrice(vehicle, price);
}

private void addLocationInfo(VehicleDto vehicle) {
   Location location = repository.findLocation(vehicle.getId());
   mapper.updateVehicleWithLocation(vehicle, location);
}

“Yes, but your log is inside the loop. The line of log will be repeated several times. You should have the total time instead”

Once I execute it, I can easily copy the logs and use an Excel file to obtain the total time of each method.

Or, I can create a HashMap where the key is a string with the step name, and the value is the total time executed in the step.

What’s important here is to have a repeatable method. Easy and fast.

Because once I identify which method consumes 80% of the time, I need to go inside this method and do it again.

Extract the Input Values into a Map

Once I’ve identified the method which slows down my request, I start applying the solution.

There may be several reasons for a method to be slow:

Querying the database inside a loop: this creates many database connections per iteration, which is a waste of time;
Searching into a list: using a list for a search system is a bad idea. It has to look for the element testing each one until the correct one is found.

What’s the solution for each case?

Store all the elements in a HashMap. Use the ID as the key, and the object as the value.

In the code of the beginning, the problem comes from too many database requests. Let’s apply the solution.

public List<VehicleDto> findVehicles(
      SearchCriteria searchCriteria) {
   List<VehicleDto> results = new ArrayList<>();

   List<Vehicle> vehicles = repository.findAll(searchCriteria);

   Map<Long, List<Image>> imagesPerVehicle = repository.findImagesPerVehicle();
   Map<Long, Price> pricePerVehicle = repository.findPricePerVehicle();
   Map<Long, Location> locationPerVehicle = repository.findLocationPerVehicle();

   for (Vehicle vehicle : vehicles) {
      VehicleDto vehicleDto = mapper.toDto(vehicle);

      this.addImagesInfo(vehicleDto, imagesPerVehicle);

      this.addPriceInfo(vehicleDto, pricePerVehicle);

      this.addLocationInfo(vehicleDto, locationPerVehicle);
   }

   return results;
}

private void addImagesInfo(VehicleDto vehicle, Map<Long, List<Image>> imagesPerVehicle) {
   List<Image> images = imagesPerVehicle.get(vehicle.getId());
   mapper.updateVehicleWithImages(vehicle, images);
}

private void addPriceInfo(VehicleDto vehicle, Map<Long, Price> pricePerVehicle) {
   Price price = pricePerVehicle.get(vehicle.getId());
   mapper.updateVehicleWithPrice(vehicle, price);
}

private void addLocationInfo(VehicleDto vehicle, Map<Long, Location> locationPerVehicle) {
   Location location = locationPerVehicle.get(vehicle.getId());
   mapper.updateVehicleWithLocation(vehicle, location);
}

This solution uses fewer requests to the database. But the requests will take more time.

Is this solution better than before?

Now it’s time to compare with the times before my modifications.

Compare the Times

If the gain is acceptable, then the solution is ready to be pushed.

If the gain is good but not enough, I must look for the next method which takes the most time. And repeat the process.

And if the request time is worse, I must revert and look for another solution.

Conclusion

Using the memoization to optimize a request may not be the solution.

But I always start using this method to improve the response time. As it’s a simple method which requires modifications only in the backend.

If the memoization is not enough, I continue with the next solution of my framework.

The Dev World – Sergio Lema