making a large lookup table

Index > Main > making a large lookup table

Author

Thread

tthsqe

Joined: 20 May 2009
Posts: 739

tthsqe

I would like to make a lookup table for around 1000-2000 quad words.
I of course would not fill in this table by hand, but have the program fill it in first. What is the best way to do this?

28 Jun 2009, 22:35

Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania

Borsuc

Fill it with what?

EDIT: by "quad words" you mean "english words with 4 characters" or "quadwords" ("word" is 16-bits number)?

29 Jun 2009, 00:19

tthsqe

Joined: 20 May 2009
Posts: 739

tthsqe

quad word = 64 bit integer
The look up table should look like

[starting address ] = 0xFFFFFFFFFFFFFFFF
[starting address + 8] = 0xFFFFFFFFFFFFFFFF
[starting address +16] = 0xFFFFFFFFFFFFFFFF
...
[starting address + bignum*8]

I don't want the program to have a chance of overwriting anything that happens to be at these latter addresses.

29 Jun 2009, 02:38

tthsqe

Joined: 20 May 2009
Posts: 739

tthsqe

I think I got it:

table db 1000 dup (0,0,0,0,0,0,0,0)

Will this set aside 1000 8-byte memory locations for table?
Is there a better way to do this to allow for faster lookup times?

29 Jun 2009, 03:36

sinsi

Joined: 10 Aug 2007
Posts: 744
Location: Adelaide

sinsi

Code:

table rq 1000

29 Jun 2009, 04:00

tthsqe

Joined: 20 May 2009
Posts: 739

tthsqe

hm...

Code:

table dq 1000

is not working but,

Code:

table  dq 1000 dup 0

is.

29 Jun 2009, 06:40

sinsi

Joined: 10 Aug 2007
Posts: 744
Location: Adelaide

sinsi

"rq", not "dq" - reserve quadword(s)

29 Jun 2009, 06:53

Borsuc

Joined: 29 Dec 2005
Posts: 2465
Location: Bucharest, Romania

Borsuc

I'm confused. You said you wanted 0xFFFFFFFFFFFFFFFF, not 0, so why use dup(0) in your examples? Use dup(-1) instead.

30 Jun 2009, 02:29

bitRAKE

Joined: 21 Jul 2003
Posts: 3420
Location: vpcmipstrm

bitRAKE

Code:

table rq .size
  .size = 1000
.
.
macro table.init {
  lea rdi,[table]
  mov ecx,table.size
  or rax,-1
  rep stosq
}

...uses less space in the executable if table is at the end of a section or in an uninitialized section. Of course, a couple more bytes can be saved in the code with:

Code:

lea rdi,[table]
mov ecx,table.size * 8
mov al,-1
rep stosb

30 Jun 2009, 09:05

tthsqe

Joined: 20 May 2009
Posts: 739

tthsqe

Quote:

I'm confused. You said you wanted 0xFFFFFFFFFFFFFFFF, not 0, so why use dup(0) in your examples? Use dup(-1) instead.

don't be confused. The intial contents of the table is irrelevent - it is initialized by the program and then used as a lookup table.

02 Jul 2009, 02:31

tthsqe

Joined: 20 May 2009
Posts: 739

tthsqe

If the start of the table is not a address that is a multiple of 8 (or 4?), will there be a penalty for misaligned memory accesses? Is there a way to fix this in fasm? The values are looked up in a performance sensitive loop.

02 Jul 2009, 02:38

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly

If the memory access crosses a cache line boundary you'll get a penalty (not sure what about a misaligned access that doesn't crosses a line on newer processors). Since some elements in the table will obviously cross a cache line (and probably a page boundary too), it is better to align always.

Well, if what you want is a LUT of quad words then this is the way

Code:

align 8 ; Perhaps could be better to use 16, 32, or 64 (the latter is the cache line size of an Athlon64)
LUT rq LUT_SIZE_IN_QWORDS

02 Jul 2009, 02:56

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum