need an optimized method

[lakshmiram.saikia]

Hi,

I need to do the following operation :

'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range. I am looking
for an optimized method to do this as this
check is going to be called in a high priority callback task, and
simply comparing the mac address will lead to
some performance issues to this task ".

Can someone guide/help me out on this ?

Sekia

[Dave Vandervies]

In article <11**********************@z28g2000prd.googlegroups .com>,
<la***************@gmail.comwrote:

>Hi,

I need to do the following operation :

'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range. I am looking
for an optimized method to do this as this
check is going to be called in a high priority callback task, and
simply comparing the mac address will lead to
some performance issues to this task ".

Can someone guide/help me out on this ?

Only compare them if they're in the range you care about.

(Or, more seriously: Figure out what you're Really Trying To Do and
what the constraints Really Are. Then measure it to see if you need to
be clever. Then check to see if there's a better way to accomplish the
goal than microoptimizing the solution you have. THEN, if you're sure
you really need to microoptimize, find somebody who knows what they're
doing to do it.)
dave

--
Dave Vandervies dj******@csclub.uwaterloo.ca

C99. C99 run. Run, 99, run.
--Joona I Palaste in comp.lang.c

[jacob navia]

la***************@gmail.com wrote:

Hi,

I need to do the following operation :

'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range. I am looking
for an optimized method to do this as this
check is going to be called in a high priority callback task, and
simply comparing the mac address will lead to
some performance issues to this task ".

Can someone guide/help me out on this ?

Sekia

if (Z >= X && Z <= Y) {
}

This needs only two integer comparisons. Hardly a big deal now.
I can't imagine that those two integer comparisons make ANY
difference in the actual speed of your program.

Why do you think that that is the case?

What measurements have you done to prove that thesis?

jacob

[Walter Roberson]

In article <46***********************@news.orange.fr>,
jacob navia <ja***@jacob.remcomp.frwrote:

>la***************@gmail.com wrote:

>'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range.

>if (Z >= X && Z <= Y) {
}

>This needs only two integer comparisons. Hardly a big deal now.
I can't imagine that those two integer comparisons make ANY
difference in the actual speed of your program.

MAC addresses are multibyte non-arithmetic types. The number of
bytes involved might be fixed for the OP's particular application,
but *in the general case* Media Access Control (MAC) sizes could vary
between media. Bytes containing binary 0's are not uncommon
in MAC addresses, so we can't just drop down to string operations.

If speed happens to be more important than storage, and the
same [X,Y] pair gets checked against often, then I would
suggest to the OP that operations could be speed up by keeping
an index per [X,Y] pair of the number of bytes in common that X and Y
have. Compare bytes from the beginning, and if there is a mismatch
in the first N bytes then the MAC is not within the range; from
N to the end, you need a range check (two comparisons instead of one.)

But if speed is very important, then it becomes important to ask what
the probabilities are of various cases; if few of the incoming
MACs will be in the range, then your optimal code would be different
than if most of the MACs will be in the range. And of course
available space is a factor too -- some things can be made faster
by using lookup tables on portions of the MACs, but is there room
for that kind of tradeoff? And is there only one [X,Y] pair or
could there be a lot of such pairs? The solution when there are
a lot of such pairs might be quite different, possibly being
time-linear in the number of bytes in the MACs rather than time-linear
in the number of such pairs to be examined; then there are the
algorithms that are bytes*log(n) in the number of pairs to be examined
but are fairly space compact...
--
"It is important to remember that when it comes to law, computers
never make copies, only human beings make copies. Computers are given
commands, not permission. Only people can be given permission."
-- Brad Templeton

[Keith Thompson]

jacob navia <ja***@jacob.remcomp.frwrites:

la***************@gmail.com wrote:

>I need to do the following operation :
'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range. I am looking
for an optimized method to do this as this
check is going to be called in a high priority callback task, and
simply comparing the mac address will lead to
some performance issues to this task ".

[...]

>
if (Z >= X && Z <= Y) {
}

This needs only two integer comparisons. Hardly a big deal now.
I can't imagine that those two integer comparisons make ANY
difference in the actual speed of your program.

You're assuming that a "mac address" is represented as an integer, or
at least as some arithmetic type.

The term usually refers to the 48-bit unique address of a network
adapter; this can usually be represented as an integer (assuming
either a C99 implementation or one that has an integer type of at
least 48 bits).

But from the way the original poster asked the question, he may be
talking about machine addresses, i.e., raw memory addresses, though
the phrase "each incremented by one" seems out of place. If so, he
needs to be aware that relational operators on pointers invoke
undefined behavior *unless* both pointers point into the same object,
or just past the end of it. (Such comparisons are likely to work as
expected in most implementations; if the OP is willing to accept code
that isn't 100% portable, the simple comparisons you suggest might do
the job.)

The OP needs to clarify just what he's talking about.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[J. J. Farrell]

On Jul 10, 11:57 am, [e-mail] wrote:

>
I need to do the following operation :

'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range. I am looking
for an optimized method to do this as this
check is going to be called in a high priority callback task, and
simply comparing the mac address will lead to
some performance issues to this task ".

Can someone guide/help me out on this ?

Has the size of the problem been measured? What is the current
implementation, and by how much do you need to speed it up?

It depends very much on how you represent the mac addresses in this
code. If it really is the case that simply comparing the addresses
will cause performance problems, then you very likely need micro-
optimizations beyond the scope of this newsgroup - they'll depend on
the instruction set in question, the cache model of the processor in
question, locations of variables in memory, the compiler you are
using, and so on.

More realistically (but perhaps less practically) if this really is a
problem you need to implement the software on a more powerful platform.

[lakshmiram.saikia]

On Jul 11, 4:19 am, [e-mail] (Walter Roberson)
wrote:

In article <46940067$0$25915$[e-mail]>,
jacob navia <[e-mail]:

[e-mail] wrote:

'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range.

if (Z >= X && Z <= Y) {
}
This needs only two integer comparisons. Hardly a big deal now.
I can't imagine that those two integer comparisons make ANY
difference in the actual speed of your program.

MAC addresses are multibyte non-arithmetic types. The number of
bytes involved might be fixed for the OP's particular application,
but *in the general case* Media Access Control (MAC) sizes could vary
between media. Bytes containing binary 0's are not uncommon
in MAC addresses, so we can't just drop down to string operations.

Thanks,and Yes, your understanding is exact.Mac address is 48 bytes of
size,
and zero mac can also be there. To give you more information, assuming
that
the I have a base mac = 00:00:00:00:00:01.I have some 24 physical
interfaces,
each having a mac such that , nth mac = base mac + n , n<=24.

This is basically real-time scenario where, the callback task will be
hit
lots of time for each incmng pkt. I need to do the following :

1. Get the incoming pkts src mac (assume that I got it)
2. If this src mac falls within base mac or last physical interface
mac, then
execute some actions.

The range checking of the src mac is what I want to optimise.
Also,since the base mac
is user configurable, the comparsion of first nth bytes will not help,
since, assume,
base mac configured by user is = 00:00:00:00:FF:FF, then next mac will
be 00:00:00:01:00:00
Now, if the cmpare the first 4 bytes, then this will fail, and i will
not be doing the chck I want to perform.!

Pls let me know what I can do more in this case.

If speed happens to be more important than storage, and the
same [X,Y] pair gets checked against often, then I would
suggest to the OP that operations could be speed up by keeping
an index per [X,Y] pair of the number of bytes in common that X and Y
have. Compare bytes from the beginning, and if there is a mismatch
in the first N bytes then the MAC is not within the range; from
N to the end, you need a range check (two comparisons instead of one.)

But if speed is very important, then it becomes important to ask what
the probabilities are of various cases; if few of the incoming
MACs will be in the range, then your optimal code would be different
than if most of the MACs will be in the range. And of course
available space is a factor too -- some things can be made faster
by using lookup tables on portions of the MACs, but is there room
for that kind of tradeoff? And is there only one [X,Y] pair or
could there be a lot of such pairs? The solution when there are
a lot of such pairs might be quite different, possibly being
time-linear in the number of bytes in the MACs rather than time-linear
in the number of such pairs to be examined; then there are the
algorithms that are bytes*log(n) in the number of pairs to be examined
but are fairly space compact...
--
"It is important to remember that when it comes to law, computers
never make copies, only human beings make copies. Computers are given
commands, not permission. Only people can be given permission."
-- Brad Templeton

[Keith Thompson]

la***************@gmail.com writes:

On Jul 11, 4:19 am, [e-mail] (Walter Roberson)
wrote:

>In article <46940067$0$25915$[e-mail]>,
jacob navia <[e-mail]:

>[e-mail] wrote:
'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range.
if (Z >= X && Z <= Y) {
}
This needs only two integer comparisons. Hardly a big deal now.
I can't imagine that those two integer comparisons make ANY
difference in the actual speed of your program.

MAC addresses are multibyte non-arithmetic types. The number of
bytes involved might be fixed for the OP's particular application,
but *in the general case* Media Access Control (MAC) sizes could vary
between media. Bytes containing binary 0's are not uncommon
in MAC addresses, so we can't just drop down to string operations.

Thanks,and Yes, your understanding is exact.Mac address is 48 bytes
of size, and zero mac can also be there. To give you more
information, assuming that the I have a base mac =
00:00:00:00:00:01.I have some 24 physical interfaces, each having a
mac such that , nth mac = base mac + n , n<=24.

[...]

A mac address is 48 bits, not 48 bytes.

So you're dealing with 48-bit numbers. Your C compiler probably
supports an integer type at least that big. Treat the mac addresses
as integers, and compare them. I doubt that there's much you can do
to improve on that.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

[santosh]

[e-mail] wrote:

<snip>

>[e-mail] wrote:
>>
>'" I have two mac addresses, say X and Y,where X is the base mac
>address, and Y is the nth mac address from X, each incremented by one.
>Now,I want to check if Z falls within [X,Y]. I need to do some check
>only when Z is one of the mac addresses in this range.
>if (Z >= X && Z <= Y)

<snip>

To give you more information, assuming that the I have a base
mac = 00:00:00:00:00:01.I have some 24 physical interfaces,
each having a mac such that , nth mac = base mac + n , n<=24.

This is basically real-time scenario where, the callback task will be hit
lots of time for each incmng pkt. I need to do the following :

1. Get the incoming pkts src mac (assume that I got it)
2. If this src mac falls within base mac or last physical interface
mac, then execute some actions.

The range checking of the src mac is what I want to optimise.
Also,since the base mac is user configurable, the comparsion
of first nth bytes will not help, since, assume, base mac
configured by user is = 00:00:00:00:FF:FF, then next mac will
be 00:00:00:01:00:00

Now, if the cmpare the first 4 bytes, then this will fail, and i will
not be doing the chck I want to perform.!

Pls let me know what I can do more in this case.

Other than what the others have said, if, after profiling, you
determine that micro-optimisation of this routine is necessary,
considering compiler intrinsics or inline assembly is a possibility.
If the platform is Intel based then I recommend comp.lang.asm.x86. You
might be able to make more efficient comparisons by using platform
specific instructions and registers.

[jacob navia]

Walter Roberson wrote:

In article <46***********************@news.orange.fr>,
jacob navia <ja***@jacob.remcomp.frwrote:

>la***************@gmail.com wrote:

>>'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range.

>if (Z >= X && Z <= Y) {
}

>This needs only two integer comparisons. Hardly a big deal now.
I can't imagine that those two integer comparisons make ANY
difference in the actual speed of your program.

MAC addresses are multibyte non-arithmetic types. The number of
bytes involved might be fixed for the OP's particular application,
but *in the general case* Media Access Control (MAC) sizes could vary
between media. Bytes containing binary 0's are not uncommon
in MAC addresses, so we can't just drop down to string operations.

They would never go beyond 64 bits, and if the compiler supports
long long (simulated) those integer comparisons will be faster
than many other algorithms if the machine is a 32 bit computer.

In a 32 bit computer we have 4 integer comparisons in the
worst case, and mostly just 2-3 will be enough.

[Duncan Muirhead]

On Wed, 11 Jul 2007 01:27:37 -0700, Keith Thompson wrote:

la***************@gmail.com writes:

>On Jul 11, 4:19 am, [e-mail] (Walter Roberson)
wrote:

>>In article <46940067$0$25915$[e-mail]>,
jacob navia <[e-mail]:

[e-mail] wrote:
'" I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by one.
Now,I want to check if Z falls within [X,Y]. I need to do some check
only when Z is one of the mac addresses in this range.
if (Z >= X && Z <= Y) {
}

<snip>

>Thanks,and Yes, your understanding is exact.Mac address is 48 bytes
of size, and zero mac can also be there. To give you more
information, assuming that the I have a base mac =
00:00:00:00:00:01.I have some 24 physical interfaces, each having a
mac such that , nth mac = base mac + n , n<=24.

[...]

A mac address is 48 bits, not 48 bytes.

So you're dealing with 48-bit numbers. Your C compiler probably
supports an integer type at least that big. Treat the mac addresses
as integers, and compare them. I doubt that there's much you can do
to improve on that.

Supposing that long is big enough, that long b is your base mac address
and that long t is your last mac address you could compute
unsigned long d = t-b before hand and then when a candidate mac address x
comes along test it with (unsigned long)(x-b) <= d (the point being that
if x>b then x-b < 0, so as an unsigned is bigger than d).
But is such a scurvy trick standard C? Will it be faster than two
compares?
Duncan

[CBFalconer]

la***************@gmail.com wrote:

>
I have two mac addresses, say X and Y,where X is the base mac
address, and Y is the nth mac address from X, each incremented by
one. Now,I want to check if Z falls within [X,Y]. I need to do
some check only when Z is one of the mac addresses in this range.
I am looking for an optimized method to do this as this check is
going to be called in a high priority callback task, and simply
comparing the mac address will lead to some performance issues to
this task

Can someone guide/help me out on this ?

What's wrong with:

if ((Z >= X) && (Z <= Y)) whatever();

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
cbfalconer at maineline dot net
--
Posted via a free Usenet account from http://www.teranews.com