Saturday, May 26, 2007


Secrets to Optimization - Function Pointers



Let me present you with a bit of code which you might find quite commonly in a program:

void function_1(type a, type b)
{
if (complex_formula())
{
method_a(a, b);
}
else
{
method_b(a, b);
}
}
...
void function_2(type *a, type *b, size_t ab_len)
{
while (ab_len--)
{
function_1(*a++, *b++);
}
}
I see this quite often in all kinds of situations. Where some repetitive action keeps calling a function which uses a static calculation which in turn does one of two things. Since this action is making many calls to a function which is doing the exact same sub action on this set of data, it really is a waste to redetermine which sub action we're dealing with for every element of data.

Imagine if a program has an option to approximate fractions from floating point using algorithm A or algorithm B, if the program repeatedly has to check which algorithm it's supposed to be using on each floating point number in a set, it is wasting time that could be spent on actually working on these numbers.

The most obvious way to speed this process up is to setup a variable which contains the result of complex_formula(), so complex_formula() itself doesn't have to be recalculated again and again, and instead we just do something like "method = complex_formula()" once, and just check "method" each time. However if we have a case where we have multiple methods, we'd have to turn this into a switch(). Once we have several methods, we'll be wasting a bit of minor but cumulative CPU cycles for every time we need to perform this action.

In order to bypass any overhead, or make the overhead insignificant, we make use of a sometimes neglected feature - function pointers. Let's rewrite the prior example:

void (*function_1)(type a, type b) = method_a;
...
void function_2(type *a, type *b, size_t ab_len)
{
while (ab_len--)
{
function_1(*a++, *b++);
}
}
With this new bit of code, method_a will be used each time. If we want to recalculate which method to use because an option was changed. then we can do something like this when need be:

function_1 = complex_formula() ? method_a : method_b;
But this complex_formula() won't have to be rechecked for each element of an array, or even overhead for comparison and jumping if we did ifs/switch on a variable.

I've looked into the difference of calling a function directly or via a pointer, and on the CPUs I looked at, the overhead was 1 cycle or even 0, meaning the overhead is negligible if any. Either way, it's less than that of a comparison and jump, and surely several of them.

If you remember some posts back where I was talking about quick sorting, I setup a sorting testing frame work like so:

struct qsorters
{
char *name;
void (*func)(void *, size_t, size_t, int(*)(const void *, const void *));
};

static struct qsorters qsorters[] = {{"AT&T", qsort_att},
{"BSD 1983", qsort_bsd2},
{"BSD 1990", qsort_bsd3},
{"BSD 1993", qsort_bsd},
{"diet libc", qsort_dietc},
{"DJGPP", qsort_djgpp},
{"glibc", qsort_gnu},
{"IBM", qsort_ibm},
{"Linux", qsort_linux},
{"Microsoft", qsort_microsoft},
{"Sun", qsort_solaris},
{"Syslinux", qsort_syslinux},
{"uClibc", qsort_uclibc},
{"insane", qsort_insane},
{"Simple", qsort_simple},
};
Now my sorting framework simply looped through the array and did the sorting tests on qsorters[i].func() instead of it needing to setup some kind of switch system to translate names into the function to call. If you want table driven methods to apply to functions, this is the way to do it. Imagine how much slower my testing framework would've been if I had to use a switch on this. This also makes the code simpler to read and write, just like arrays make more sense than x1. x2. x3. etc...

Function pointers are a wonderful thing to use whenever you have multiple functions which are the same black box, which when on the same input offer the same output, just use different methods internally.

This also extends well to when mixing with other kinds of optimizations. Quite often people try to optimize critical sections of their code using hand tuned assembly. Now on the x86 platform, there exists several instruction sets which can be used for optimization that not every CPU has, for example, MMX, 3DNow!, SSE, SSE2, etc...
If one wanted to offer good assembly optimizations for something, I all to often see scattered across programs code like this:

void func()
{
if (detect_sse2())
{
func_sse2();
}
else if (detect_3dnow())
{
func_3dnow();
}
else if (detect_mmx())
{
func_mmx();
}
else
{
func_i386();
}
}
If func() is called say 10,000 times a frame in a video processing program, it really lowers the overall FPS that could be processed if instead the following method was used:

void (*func) = func_i386;
void (*func2) = func2_i386;
etc...

void instructions_detect()
{
if (detect_sse2())
{
func = func_sse2;
func2 = func2_sse2;
}
else if (detect_3dnow())
{
func = func_3dnow;
func2 = func2_3dnow;
}
else if (detect_mmx())
{
func = func_mmx;
func2 = func_mmx;
}
}
With this, instruction_detect() can be called when the program is started, or the library is initialized, and since the instruction set is not going to change in the middle, you just call this once and forget about it. With this, you can achieve optimal speed for any given processor in a program, without wasting any speed for overhead, aside from an initial call.

27 comments:

DeFender1031 said...

I hate how underused function pointers are. I mean, as you know, I never would have learned them if Nach hadn't taught me, as most teachers tend to skip them. I think it's great that someone is finally trying to get them out there.

Give the wife and adorable little cuties my regards.

sinamas said...

Wait a minute. You mean there're actually c programmers that don't use function pointers?

Unknown said...

Yes there are plenty that don't. If you look at source code to many open source projects, you think to yourself on many occasions that they could have wrote the code much better using function pointers. I hope Insane Coder blogs again about function pointer uses, it's an important subject.

younus saleem saifullah said...

whenever I hit any "function pointer" tutorial I used to come across an example of "HOW TO REPLACE A SWITCH"....it was insane the way most examples were programmed.
I had almost come toa conclusion that function pointers are not all that useful.

Thanks to this blog now I do know the real power of function pointers. I made use of the same in "HOW TO REPLACE A SWITCH" and it gave wonderful results.

Thanks for the explaination...:)

Unknown said...

thanks a lot for sharring a very successful

Anonymous said...

xxx whatsapp group links
girls whatsapp group invite links
latest adult18 whatsapp group links
join adult whatsapp group link
active adult whatsapp groups
hot aunties whatsapp group collection
best adult whatsapp group
russian adult whatsapp groups collection
Pakistani adult whatsapp group link
join latest whatspp groups

ravi kumar said...

Thanks for provide great informatic and looking beautiful blog, really nice required information & the things i never imagined and i would request, wright more blog and blog post like that for us. Thanks you once agian

Birth certificate in delhi
Birth certificate in ghaziabad
Birth certificate in gurgaon
Birth certificate in noida
How to get birth certificate in ghaziabad
how to get birth certificate in delhi
birth certificate agent in delhi
how to download birth certificate
birth certificate in greater noida
birth certificate agent in delhi
Birth certificate delhi

keanna said...

Endless supply of AWS Training Sessions in Gurgaon, wannabes can without much of a stretch form subject abilities in each module to convey a most streamlined arrangement. This for the most part empowers the group of spectators to use aptitudes in each idea and become specialists in each propelled cloud based arrangement and moving existing remaining burdens to the cloud.

For More Info:- AWS Institute in Gurgaon

maan said...

Nice article thanks for sharing valuable info
Lucky Patcher Apk

sohbet.cm said...

sohbet www.yuvam.net
sohbet www.sohbet.cm

MBBS in Philippines said...

UV GULLAS COLLEGE OF MEDICINE is one of Top Medical College in Philippines in Cebu city. International students have the oppertunity to study medicine in phillipines at affordable cost and world class University. The college has successful alumni who have achieved well in the fields of law, business, politics, academe, medicine, sports and other endeavors. At University of the Visayas, we prepare students for a global competition.

Direct MBBS Admissions Open: 2020-21
Mobile No: +91 90329 55688
Apply Now: https://www.careerplus.org.in/philippines-medical-college/uv-gullas-college-of-medicine

sohbet said...

Laklak Sohbetler de sakin olan yada içine kapanık olan insanlar sohbet etmezler diye düşünmeyin asla. Onların da kafa dengi insanlar elbette ki var. İçerisinde saklamış oldukları duyguları ortaya çıkaran insanlar…

https://forum.hayalsohbet.net

hont said...

NEET chemistry
IB chemistry
IGCSE chemistry
CBSE chemistry

Addons said...

opencart development in usa
woocommerce development in usa
search engine optimization services in usa
local seo services in usa
national seo services in usa

Free Chat said...

Thank you for sharing great information also Omegle may useful for talk to stranger people

alex said...

A common way of implementing OO-like code encapsulation and polymorphism in C is to return opaque pointers to a structure containing some function pointers. This is a very frequent pattern for example in the Linux kernel. Using function pointers instead of function calls introduces an overhead which is mostly negligible due to caching, as has already been discussed in other questions. omegle

Unknown said...

https://ometv.icu/
Bazoocam Chatroulette Alternative
Omegle Alternative
Chatroulette

xingxing said...

abrigo aviador mujer abdomen
gucci forocoches
sonic 3 and knuckles juego online
short de bain islamique
stihl klamotten
brabus rocket 900 amazon
new balance icarus
sonnenbrille herren mit seitenschutz
hoodie pepe jeans cyan
shorts fitness feminino
melhores marcas de mochilas masculinas
quadri da disegnare amazon
aharry potter x vans
culle e passeggini per neonati amazon
camisa da ferroviária
galocha rosa feminina
deichmann bolsos
bolso de mano de hombre guess entusiasta
tenda da sole spiaggia amazon
nike pegasus 94
Nike Air Force 270
borraccia decathlon amazon
sostituzione cinghia distribuzione seat mii
veste per battesimo amazon

xingxing said...

calzoncillos puma hombre
adidas originals panna scarpe uomo basse
grossista condizionatori
costumi interi amazon
vestito da elsa disney
adidas yeezy semi frozen yellow on feet
second hand golf 5 gti for sale
piumini daunenstep amazon
pittura x pareti amazon trascorrere
fiore garofano amazon
air force 1 nike outfit men basket
nike air zip up hoodie
king kong jeans
zapatillas running galaxy 4 azul marino mujer adidas
blazer basicos mujer
nike air max de bebe principal opción
zapatos de charol mujer con taco
nike metcon flyknit 3 para running
bolsas para comprimir equipaje
chanclas new balance niña
nike pegasus grey and green
amazon sandalias reef
polo simulator

diamondsymons2 said...

casquette ford Immigration
chaussure carla moreau
triciclo usato milano
chaussures de sécurité facom
foot locker nike react element
scatola protezione stagna
nike metcon 5 rojas
zapatillas de agua niña
veste velour carhartt
damen lack schnürer
cappotto rosso scarpe nike
fiore garofano amazon
nike presto extreme pas cher
nike pegasus 94
shorts fitness feminino
nike t shirt tumblr
quadri da disegnare amazon
chinelo slide da melissa
tenis all star feminino branco couro
calzoncillos puma hombre
veste per battesimo amazon
nike air force modelo agotado
cartera levis hombre
filtre pour aspirateur samsung sc4780
autoradio gps vdo
nike tribute veste
soldes chaussures homme caterpillar hiver cafétéria
amazon sandalias reef
chanclas new balance niña
kit de creation de bracelets utilisation
wc suspendu mural amazon
foulard en soie homme
all star converse star player
paragliding přilby
nike anzug nba rot
camisa da ferroviária
tapie adidas credit lyonnais
gucci handbags uk
air force 1 nike outfit men basket

bedortheadora said...

borraccia decathlon amazon
camisa ponte preta aranha
sandalias de esparto mujer
kiabi bottine femme
polo lacoste ton sur ton
pepe jeans tami
crampon vissé adidas
brassiere garcon
vestido de niña rosa palo
maglia termica nuoto bambina
adidas zx flux adv virtue sock w
nike cortez prm
beutel zipper amazon
nike tanjun damen weiß 44
scarpe pirelli uomo impedire
polo ralph lauren jeanshemd damen
risparmiare batteria iphone ios 12
style année 80 femme
Nike Air Force 270
kimono en jean
pantaloni puma femei pollice Linea di metallo
shein camicie donna cameriera
bañador neopreno mujer oysho
sudadera nike vintage
giacca da prestigiatore
sandalias courofeito a mao
grossista condizionatori
piumini daunenstep amazon
zapatillas cruyff mujer
valentine gauthier chaussures
nike huarache og colorways
pull lacoste col montant activer
zirkus jacke herren amazon
maglia as roma blu
tabouret pour toilette amazon
puma calçados femininos desvaneça
adidas duramo 7 precio
nike air force one rot schwarz

qwe said...

nike sb prod x
gucci leather wristband
botas australianas mustang
magnum pi jeans
nike pegasus 94
scatola protezione stagna
shein camicie donna cameriera
nike les halles
nike blazer low 3d
vestido de niña rosa palo
giacca da prestigiatore
sapatenis masculino elastico
sujetador media copa abierto
polo shirt juventus
ladies summer shorts
gucci slides cheap
sandalias agua cerradas
survetement adidas homme militaire
nike t shirt tumblr
nike tanjun damen weiß 44

qwe said...

tumbona terraza ikea
nike zoom strike sprinter
gants si assault factory pilot noir oakley
camisa cuadros franela mujer
galocha rosa feminina
adidas run falcon on feet
ghete galbene piele
hama stiftplatte einhorn amazon
moleton nike preço
veste velour carhartt
bañador neopreno mujer oysho
jogging fille 14 ans adidas
melhores marcas de mochilas masculinas
beistelltisch mit stauraum
nike air max 97 silber
adidas niño verde agua
béret a pompon bretelles uniforme
rompecabezas de obras de arte para arma
venta de bicicletas para ejercicio
sudadera nike vintage
lidl online dirndl
adidas noir doré
foot locker nike react element
filtre pour aspirateur samsung sc4780
adidas stabil x junior

bedortheadora said...

nike air max de bebe
sfera vestido flecos mostaza
filtre pour aspirateur samsung sc4780
tende doccia milano amazon
adidas superstar purple
jogging fille 14 ans adidas
af1 louis vuitton
sandália rasteira bottero
zapatillas bimba y lola outlet
chinelo slide da melissa
leggings mit spitzenabschluss
cartera levis hombre
ropa de crossfit nike
camisa da ferroviária
jersey rombos hm
gucci forocoches
sudadera nike vintage
shirt mit schnürung am ausschnitt
gants si assault factory pilot noir oakley
hama stiftplatte einhorn amazon
outlet nike floresta
sacoche lv district
nike hoodie xxl ebay
timberland herren 3 eye
kit citofono terraneo amazon
nike presto extreme pas cher
gucci handbags uk
nike huarache kobe bryant
tight leggings adidas
bolsas de deporte nike negra hombre grande
style année 80 femme
adidas personalised shoes
sandalia rafaela melo
survetement adidas homme militaire
vestido de niña rosa palo
adidas noir doré
adidas rock climbing
adidas boost 350 black

alex said...

Great content and Thanks for share with us this valuable information check also

Thanks For Sharing Awesome Post!

https://mail.tcs.com
AlloTalk online
BTinternet Mail
hotmail.com

Unknown said...

I will do it later!! ometv nirvam

MBBS in Philippines said...

Wisdom Overseasis authorized India's Exclusive Partner of Southwestern University PHINMA, the Philippines established its strong trust in the minds of all the Indian medical aspirants and their parents. Under the excellent leadership of the founder Director Mr. Thummala Ravikanth, Wisdom meritoriously won the hearts of thousands of future doctors and was praised as the “Top Medical Career Growth Specialists" among Overseas Medical Education Consultants in India.

Southwestern University PHINMAglobally recognized university in Cebu City, the Philippines facilitating educational service from 1946. With the sole aim of serving the world by providing an accessible, affordable, and high-quality education to all the local and foreign students. SWU PHINMA is undergoing continuous changes and shaping itself as the best leader with major improvements in academics, technology, and infrastructure also in improving the quality of student life.