DEV Community: Adwait Thattey

Optimizing C++ vector for 2x performance !

Adwait Thattey — Mon, 01 Aug 2022 06:08:00 +0000

std::vector is perhaps one of the most used data structures in C++. It provides a dynamic array that is very easy to use.
But the simplicity comes at a slight performance cost that is often ignored. It is however really simple to optimize this data-structure and get a performance boost.

First lets look at the problem.

Here I am creating a simple class that keeps track of the constructor, destructor and the copy constructor calls.




class Sample
{
public:

Sample(int id)
{
     ++m_constructor_count;

      m_id = id;

}



~Sample()
{
     ++m_destructor_count;
}



Sample( const Sample& o)
{
      ++m_copy_constructor_count;
}



   int m_id = -1;

   static unsigned long m_constructor_count, m_destructor_count, m_copy_constructor_count;



};



// initialize counts to 0

unsigned long Sample::m_constructor_count = 0;
unsigned long Sample::m_destructor_count = 0;
unsigned long Sample::m_copy_constructor_count = 0;

Now lets create a vector , add 3 elements to it and print the calls



std::vector<Sample> vec;

vec.push_back( Sample(1) );
vec.push_back( Sample(2) );
vec.push_back( Sample(3) );

We have 3 Constructor calls but 6 Copy Calls and 9 Destructor calls !

Constructor calls are expected, we are creating 3 elements. But where are these copy and destructor calls coming from ??

Well, the destructor calls are just a sum of constructor and copy. So lets look at the copy calls.

This is due to 2 problems with std::vector

1. Copy while insertion

2. Copy while resizing

Lets look at 1st problem.

1. Copy while insertion

Look at this statement

vec.push_back( Sample(1) );

Here we are first creating an object of class Sample, then when it is inserted to the vector, it is copied to the vector's memory.

This is the source of 3 copy calls as we have 3 items.

Since we just want to insert element into vector, is there any way to directly create the object in vector's memory?

Yes there is!

std::vector provides another method emplace_back .

Using this method, we can directly pass the arguments that we would have passed to the constructor and the vector directly creates the object in its memory

vec.emplace_back( 1 );

Lets look at the results now

We have reduced 3 copy calls

What about the remaining 3 calls?

This brings us to the 2nd problem

2. Copy while resizing

A vector is a dynamic array. Meaning, the compiler doesn't know about it's size beforehand.

So the compiler starts with 1 and dynamically increases the capacity of vector as we add to it.

This means that every time the vector runs out of it's capacity, it needs to resize. This resize operation copies all the elements from 1 memory location to another.

Lets track how the 3 copies are happening



std::vector<Sample> vec;

// initialized with capacity 1



vec.push_back( Sample(1) );

// insert 1 element. capacity is 1, size is 1. 



vec.push_back( Sample(2) );

// exceeded capacity. Resize operation. Copy the 1 element in the vector to new location. New size and capacity is 2

// 1 Copy


vec.push_back( Sample(3) );

// exceeded size. Resize vector. Copy the 2 elements in the vector to new location. New size is 3

// 2 Copies



Total copies due to resize: 3

This is the source of 3 additional copy calls.

Does this mean that n copies will take place every time we insert a new element?

Well no. The system can allocate additional memory assuming that we are adding more elements.

While this can change compiler to compiler, memory is usually allocated in 2s power.

For example, when we add 3 elements, memory is allocated for 4, adding 5th allocates for 8, adding 9th allocates for 16, adding 17th for 32 and so on. Take a look at this

This means that not only are we causing unnecessary copy calls, we are also potentially using up additional memory that is not needed. For example in the above case, even if we had only 129 elements, we were using the memory for 256 elements.

So, is there a way to avoid this?

Yes there is.

We just need a way to tell the compiler how many elements we are planning to insert so that system can reserve the needed memory beforehand reducing the copy calls.

For this, std::vector provides another method. reserve

This allows us to specify how many elements we are planning to insert and causes the vector to allocate that much memory beforehand

Lets modify our code to use this



std::vector<Sample> vec;

vec.reserve(3); // specify we are going to insert 3 elements



vec.emplace_back( 1 );
vec.emplace_back( 2 );
vec.emplace_back( 3 );

We have successfully removed all the copy constructor calls.

Performance Improvement

Now as a final step, lets also see how much performance improvement can this lead to.

For this I am going to count the number of clock ticks utilized for inserting 10 million elements

First without using emplace and reserve

732483 ticks

(Also notice we have 26 million additional copy calls for just 10 million elements!)

Now using emplace and reserve

386635 ticks

That's more than 2x performance improvement. And best part , it did not require a lot of effort.

Summary

A copy operation takes place when we use push_back to insert into vector and multiple copy operations take place whenever the vector runs out of space and resize takes place.

Use emplace_back instead of push_back wherever possible.

If the number of elements we are going to insert is known before hand, use reserve to specify the capacity.

Even if exact size is not known, it might still be worthwhile to use reserve with some known lower bound for the number of elements.

Credits

This video by "The Cherno" on Youtube was the source of inspiration for this post.

https://www.youtube.com/watch?v=HcESuwmlHEY

This channel has lots of neat tips and tricks for C++. Please like this video and subscribe to his channel.

The Cherno - YouTube

Building an Event Listener SPI (Plugin) for KeyCloak

Adwait Thattey — Fri, 20 Dec 2019 15:30:09 +0000

In this blog, I will talk about how to build an event listener plugin (called an SPI) for KeyCloak

So, what is Keycloak?

Keycloak is an Open Source Identity and Access Management Framework built by RedHat. It provides a lot of advanced features like SSO, Social Auth, support for multiple auth protocols, etc. Read more here: https://www.keycloak.org/

But one of the most important features is the ability to extend any functionality of KeyCloak by simply building a plugin.

During my internship this summer, we needed to log all the events of users (and admins) happening within KeyCloak and send them to external systems for analysis. This is needed in many situations. (one example is if you are using an external SIEM to log and analyze incidents).

By default, KeyCloak logs don't contain user/admin events. And even if we enable that, it would be difficult to build an external system which monitors and parses the logs to extract required events. Instead, we can build a plugin for KeyCloak to hook into the system and do "something" whenever an event occurs (In our case, fire external API calls)

So, let's build one :)

Note: The entire code for the event listener is available here.

adwait-thattey / keycloak-event-listener-spi

A sample event listener SPI for keycloak

I would be using Maven here for managing dependencies and building project.

So let's get the pom.xml sorted out first.

(If you are not familiar with Maven, we use a pom.xml file in Maven to list all the project details including all the dependencies)

(if the above gist is not visible, you can find the file here

In pom.xml, we define the parent details, project name Sample Event Listener), version, artifact-id (here sample_event_listener), dependencies and build configuration.

The next step is to implement the SPI. For this, we need to implement 2 classes. Provider and ProviderFactory

so let's create our package in src/main/java.
Here the package name is com.coderdude.sampleeventlistenerprovider.provider

coderdude : because my dev alias is coderdude :D

sampleeventlistenerprovider: Could be shorter but let's leave it at that

provider: The last provider is there because there can potentially be other modules that you use in your provider.

Now this package is going to contain the 2 above discussed classes.
The Provider class contains the actual logic of the plugin. The ProviderFactory is a wrapper that initializes the provider. The difference is important.

The Factory is initialized only when KeyCloak is started. A new instance of Provider is created by Factory every time required. (In our case every time an event occurs)
Only 1 instance of Factory will exist. Multiple providers can exist at the same time (say 2 events occur at the same time).
Providers are destroyed as soon as they complete their tasks. The Factory exists as long as KeyCloak is running.
Any error in Factory will crash KeyCloak. An error in Provider will simply go to the logs and rest of Keycloak will function normally

So let's start by creating a Provider.
The name of the class will be SampleEventListenerProvider which implements the EventListenerProvider interface (This interface is provided by KeyCloak)

package com.coderdude.sampleeventlistenerprovider.provider;

import org.keycloak.events.Event;
import org.keycloak.events.EventListenerProvider;
import org.keycloak.events.admin.AdminEvent;

import java.util.Map;


public class SampleEventListenerProvider implements EventListenerProvider {

    public SampleEventListenerProvider() {
    }


}

Keep these imports for now. We will need them.
So here, we are just going to print all the events to the console. All events are provided by 2 classes: org.keycloak.events.Event and org.keycloak.events.admin.AdminEvent
The normal events occur whenever a normal user does something. Admin events occur when administrators do something.

We need to write appropriate methods to convert these class objects to readable strings.
Here is the method to build string for an Event

We are capturing all the parameters, errors and details. (hence the map, because the details is an array)

private String toString(Event event) {

        StringBuilder sb = new StringBuilder();


        sb.append("type=");

        sb.append(event.getType());

        sb.append(", realmId=");

        sb.append(event.getRealmId());

        sb.append(", clientId=");

        sb.append(event.getClientId());

        sb.append(", userId=");

        sb.append(event.getUserId());

        sb.append(", ipAddress=");

        sb.append(event.getIpAddress());


        if (event.getError() != null) {

            sb.append(", error=");

            sb.append(event.getError());

        }


        if (event.getDetails() != null) {

            for (Map.Entry<String, String> e : event.getDetails().entrySet()) {

                sb.append(", ");

                sb.append(e.getKey());

                if (e.getValue() == null || e.getValue().indexOf(' ') == -1) {

                    sb.append("=");

                    sb.append(e.getValue());

                } else {

                    sb.append("='");

                    sb.append(e.getValue());

                    sb.append("'");

                }

            }

        }


        return sb.toString();

    }

Of course, this is a very naive implementation. What we actually did was define methods to wrap these events in other objects and make API calls to external systems. But this will work for now.
We can build a similar method for AdminEvent. You will find it in the main full code.

Once this is done, we need to override 2 methods provided by the
EventListenerProvider interface. These are onEvent and close.

Here it is

    @Override
    public void onEvent(Event event) {

        System.out.println("Event Occurred:" + toString(event));
    }

    @Override
    public void onEvent(AdminEvent adminEvent, boolean b) {

        System.out.println("Admin Event Occurred:" + toString(adminEvent));
    }

    @Override
    public void close() {

    }

The onEvent is the actual method called whenever an event occurs. We need to overload onEvent twice to capture both Event and AdminEvent.
Finally, the close method is called just before the class is destroyed. Sort of like a destructor. We need to override it even if we don't need to use it.

You can find the full class code (along with string implementation for AdminEvent) here

Next step is to implement the ProviderFactory
The name of the class is SampleEventListenerProviderFactory which implements EventListenerProviderFactory

Here is the code:

(if the above gist is not visible, you can find the file here

We override multiple methods here. The main ones are the create and getId. The create method should initialize and return an instance of provider (in our case SampleEventListenerProvider). The getId should return a string with the name of the plugin

The next and the final task is to provide a link to our class. For this we need to create resources.
create a folder named resources in src/main (alongside java folder)
Now create the following file in resources/META-INF/services/ named org.keycloak.events.EventListenerProviderFactory . Note that full path to location of file is src/main/resources/META-INF/services/org.keycloak.events.EventListenerProviderFactory

This file just contains one line with the package and name of our factory class

com.coderdude.sampleeventlistenerprovider.provider.SampleEventListenerProviderFactory

That's it. We have written the plugin. Now let's build and package it.
I have used maven to build and package

Once packaging is complete, you should see the jar and sources in the target directory
Here is my final directory structure

We will only need the sample-event-listener.jar

--
Now it's time to deploy the plugin to KeyCloak.

Let's get setup with a KeyCloak first. You will find the getting started guide here https://www.keycloak.org/docs/latest/getting_started/index.html.

Quickly download and create an admin user and login to KeyCloak.
Now let's create a new realm named newrealm and add a user named newuser001 in the new realm.

Let's also create a password for this new user

It's time to deploy our awesome plugin

The deployment process is pretty straightforward. We need to copy the sample-event-listener.jar to $KEYCLOAK_DIR/standalone/deployments/ where $KEYCLOAK_DIR is the main KeyCloak directory (after unzipping)

KeyCloak supports hot-reloading. So as soon we copy the jar file, keycloak should reload and deploy the plugin. But just to be sure, let's restart the Keycloak server.

You should see a line like this

Deployed "sample-event-listener.jar" (runtime-name : "sample-event-listener.jar")

Now we need to allow this plugin to listen to events.
Go to newrealm->manage->events->config or this url /auth/admin/master/console/#/realms/newrealm/events-settings Make sure to replace newrealm with the name of the realm you created

In the config, event-listeners, add sample_event_listener to the list and hit save.

Now our plugin should be able to capture all events.

Lets test this

You should see an event occuring in the console

17:03:01,797 INFO  [stdout] (default task-5) Event Occurred:type=LOGIN, realmId=newrealm, clientId=account, userId=efc09972-6166-4ed6-9ca0-15c030e47f54, ipAddress=127.0.0.1, auth_method=openid-connect, auth_type=code, redirect_uri=http://localhost:8180/auth/realms/newrealm/account/login-redirect, consent=no_consent_required, code_id=78db58ed-3c99-4d42-aced-b69873c59f12, username=newuser001

Logout should also be captured

17:03:51,211 INFO  [stdout] (default task-5) Event Occurred:type=LOGOUT, realmId=newrealm, clientId=null, userId=efc09972-6166-4ed6-9ca0-15c030e47f54, ipAddress=127.0.0.1, redirect_uri=http://localhost:8180/auth/realms/newrealm/account/

Trying to login with incorrect password is also captured (because we were also capturing errors)

17:04:04,505 WARN  [org.keycloak.events] (default task-5) type=LOGIN_ERROR, realmId=master, clientId=security-admin-console, userId=null, ipAddress=127.0.0.1, error=user_not_found, auth_method=openid-connect, auth_type=code, redirect_uri=http://localhost:8180/auth/admin/master/console/#/realms/newrealm/users, code_id=59a85ee0-a8f6-4fad-8667-f72de2da18fd, username=newuser001

Looks like this in my console

Voilà! Our plugin is able to capture events

Wrapping Up:

Once again, the entire code is available here:

adwait-thattey / keycloak-event-listener-spi

A sample event listener SPI for keycloak

This is a very basic example. We can do lots more. There is a lot more useful information that keycloak events provide that can be captured. Like current realm, ip address of the person trying to login, access token IDs if it is an api login, etc.

If you liked this blog, hit like :)

Bye!

Adwait Thattey,

https://adwait-thattey.github.io/