|
We have a device that returns data from a 2D grid thus each data value is indexed by its row and column. The number of rows and columns is not fixed, as the device can be reconfigured, but in normal use the number of rows and columns does not change. We store the data values in memory for subsequent retrieval.
Our problem is how to convert a row + column pair {x,y} into an address in the memory. This sounds trivial:
offset = x * (total_number_of_columns) + y;
However, we have to do this very very quickly, and using as little processor power as possible. A multiplication is not good. We do not need to store the values contiguously as row, row, row etc. We do have limited memory so cannot be too wasteful.
One way is to store the data values in a grid whose number of columns is always a power of 2. Thus if our device generates 20 rows and 50 columns of data, we store them in a 20 rows by 64 columns grid. This means the data is not packed tightly in memory. To convert {x,y} into a memory location:
offset = x << 6 + y;
The quickest way I can think of is to use a look up table:
offset = lookup[x] + y;
Thus lookup is the offset to the start of each row in memory.
So, my question is how can we do this as fast and simply as possible? Is there a quicker way?
|
|
|
|
|
The performance of integer multiplications depend on the used CPU architecture and generation.
With most x86 and compatible CPUs integer multiplications are 2 - 4 times slower than additions which can be usually ignored. Using a lookup table will be then not significantly faster or even slower.
However, with other (mainly RISC) CPU's, the operation can be up to 40 times slower than additions.
Quote: The quickest way I can think of is to use a look up table
The quickest way is using a shift operation because that is executed on registers while a lookup table requires loading from memory.
Just compare the methods (in pseudo code):
; Classic method
load r1, x
mul r1, total_number_of_columns
add r1, y
; Shift
load r1, x
shl r1, shift_count
add r1, y
; Lookup table
load r1, x
; Assuming item size is a power of 2
; Otherwise a multiplication is used here!
shl r1, sizeof(item)
; EDIT: Must be of course according to the table item size
shl r1, TABLE_ITEM_SIZE_SHIFT
load r1, [lookup_table + r1]
add r1, y Note that some of the above operations might require two assembly instructions (especially on RISC CPU's) when operations can be only performed on registers and not with memory addresses.
modified 29-Mar-18 9:00am.
|
|
|
|
|
|
There may be, depending on the processor and number of columns and size of elements. Some processors give fast access to separate bytes of a register (or in the first place form a larger register by adjoining several smaller registers), then perhaps you can form an address almost for free by creating y in the low byte and x in the high byte of the address (likely with an offset otherwise the matrix has to start at 0). This applies to z80 and 8086 and probably some other old CISC architectures (not modern x86 though - it's still possible but no longer actually fast). On a RISC architecture that sort of trick usually doesn't exist. It also typically wastes a lot of memory (you can use the gaps of course but they're fragmented).
|
|
|
|
|
Before using such micro-optimisations, I would ensure that we have used all higher-level optimisations, first. For example:
- How are the data received?
Are they stored in memory in order of reception, or does some processing (e.g. address calculation) need to be performed? - How are the data processed?
Is the access pattern sequential? random?
If a single pass through the data is performed, is it possible to store the data (see question 1 above) in the order of processing, and thereby avoid all indexing?
You may be able to think of other optimisations, based on your knowledge of the hardware and the problem.
Ad astra - both ways!
|
|
|
|
|
Can you please suggest me Best Free tool to detect
1. Application Hang issues in C++ code
2. Memory leaks/ access violation
|
|
|
|
|
|
Using Code Gear /RAD studio. Please advise
|
|
|
|
|
I had a memory allocated out side a try block and I am trying to delete in finally?
Should there be any issue with this. I am getting access violation while deleting
char *heap = new char [50];
try
{
......
}
finally(...)
{
delete[] heap;
}
|
|
|
|
|
It should work when not modifying (which includes deleting) the heap pointer inside the try block.
If you are not doing such (just comment the code inside the try block to check it), you should tell us which compiler you are using because finally is not defined by the C++ standard.
|
|
|
|
|
I am using RAD Studio code gear
|
|
|
|
|
So it is the BCC compiler. According to the __finally (C++) - RAD Studio[^] it should be __try and __finally. When omitting the leading underscores the code should not even compile because try requires a catch and __try requires an __except or __finally.
Is it still not working with the correct syntax and an empty __try block?
Then you might ask this in a BCC specific forum like Recent Topics - Forum - Embarcadero Community[^].
|
|
|
|
|
I am getting an error in a windows include winioctl.h
typedef union {
USN_RECORD_COMMON_HEADER Header;
USN_RECORD_V2 V2; <===
USN_RECORD_V3 V3; <===
USN_RECORD_V4 V4; <====
} USN_RECORD_UNION, *PUSN_RECORD_UNION;
for the 3 lines pointed to by the errors the code built find with the windows sdk 8 I migrated the application to windows 10 and am using the windows 10 sdk
Thanks
|
|
|
|
|
ForNow wrote: ...for the 3 lines pointed to by the errors...
And that error would be what?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
|
|
|
|
|
C2143 syntax error missing ':' before constant the error might make sense if
USN_RECORD_COMMON_HEADER wasn't defined but it is a few lines above
|
|
|
|
|
But are
USN_RECORD_V2
USN_RECORD_V3
USN_RECORD_V4
defined? That's where I'd look, given your original error messages.
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
typedef USN_RECORD_V2 USN_RECORD, *PUSN_RECORD;
typedef struct {
DWORD RecordLength;
WORD MajorVersion;
WORD MinorVersion;
FILE_ID_128 FileReferenceNumber;
FILE_ID_128 ParentFileReferenceNumber;
USN Usn;
LARGE_INTEGER TimeStamp;
DWORD Reason;
DWORD SourceInfo;
DWORD SecurityId;
DWORD FileAttributes;
WORD FileNameLength;
WORD FileNameOffset;
WCHAR FileName[1];
} USN_RECORD_V3, *PUSN_RECORD_V3;
ypedef struct {
USN_RECORD_COMMON_HEADER Header;
FILE_ID_128 FileReferenceNumber;
FILE_ID_128 ParentFileReferenceNumber;
USN Usn;
DWORD Reason;
DWORD SourceInfo;
DWORD RemainingExtents;
WORD NumberOfExtents;
WORD ExtentSize;
USN_RECORD_EXTENT Extents[1];
} USN_RECORD_V4, *PUSN_RECORD_V4;
|
|
|
|
|
ForNow wrote: C2143 syntax error missing ':' before constant the error might make sense if
USN_RECORD_COMMON_HEADER wasn't defined but it is a few lines above
Could you post these "few lines"?
|
|
|
|
|
Here is the definition USN_RECORD_COMMON_HEADER
typedef struct {
DWORD RecordLength;
WORD MajorVersion;
WORD MinorVersion;
} USN_RECORD_COMMON_HEADER, *PUSN_RECORD_COMMON_HEADER;
|
|
|
|
|
Have a look in Winioctl.h to check the definitions of these types. My version compiles them fine on VS2017 and Windows 10.
|
|
|
|
|
Check the typedefs of the three structures that fail for mutual non standard members.
A candidate is the USN member.
Do you have a define directive using the same name anywhere in your project?
If that does not help enable the creation of preprocessor output files. Then you can check what the compiler "sees".
|
|
|
|
|
|
i was going through a article about friend function and then in i came across this code:
#include <iostream>
using namespace std;
class Distance
{
private:
int meter;
public:
Distance(): meter(0) { }
friend int addFive(Distance);
};
int addFive(Distance d)
{
d.meter += 5;
return d.meter;
}
int main()
{
Distance D;
cout<<"Distance: "<< addFive(D);
return 0;
}
in the above code what is
Quote: Distance(): meter(0) { }
and how is a object of class distance is able to access a private member ?Quote: int addFive(Distance d)
{
//accessing private data from non-member function
d.meter += 5;
return d.meter;
}
Thank you.
|
|
|
|
|
|
You should get hold of a good C++ book. Probably the best would be the one written by Bjarne Stroustrup[^]
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
