1 dimensional array to act like a 2d one?
BlitzMax Forums/BlitzMax Programming/1 dimensional array to act like a 2d one?
| ||
| I know I've done this before, but I've forgotten the math on how to do this. because of the way I've coded, I have a 1 dimensional array, but the data actually represents a 2d array. So instead of a 10 by 10 set of array elements, there's just a set of 100 to represent the data. I'm trying to wright a function that can take 2 indexes as if it's a 2d array and convert it to the index on the 1d array and retreive the value. Any ideas? |
| ||
This should do itarray[X + Y * WIDTH] |
| ||
If the 2 indexes are stored in the 1d array as a string and separated by a comma (ie... "Health,100"), you could extract them by using the split command like this:Local index$[] = array[0].split(",")Then index[0] would be the first value and index[1] would be the second value etc. EDIT: Something tells me grable has the correct answer. |
| ||
| At the expense of some memory, you could get rid of the x+y*w math which may save some if your array usage is intensive (tho I haven't tested the performance diff). Just make a lookup table!
local lookup:int[100]
local x:int,y:int,w:int=10
for local t:int=0 to 99
lookup[t]=x+y*w
x:+1
if x>9
x=0
y:+1
endif
next
for local t:int=0 to 99
print your_1d_array[lookup[t]]
next
(untested :P) |
| ||
| Ha,Ha,Ha.. :) @CS_TBL. I don't know. But isn't that code the same as this:
for t = 0 to 99
print your_1d_array[t]
next
|
| ||
| Hmmmmmmmm... perhaps I wasn't fully awake yet ^_^ Well ok: lookup table should be 2d ofcoz, and each item points to a 1d-location. ^_^ |
| ||
| One would think that it is faster to use x+y*width (with possible optimization) than a lookup table. |
| ||
| Maybe.. dunno, haven't checked. How would you optimize x+y*w btw? |
| ||
| Maybe.. dunno, haven't checked. How would you optimize x+y*w btw? The main optimization is getting rid of the multiply. If the WIDTH is power of two, you can use left shifting. Print (3 + 4 * 256) Print (3 + 4 Shl 8) If its not you can use a collection of shifts and additions by splitting up the number into its power of two components. Print (3 + 4 * 320) Print (3 + (4 Shl 8) + (4 Shl 6)) ' 3+(4*256)+(4*64) |
| ||
| Here is 3D position functions for determining a 1D position and visaversa I use it in junction with bytereading and writing. Function GetMapP(x,y,z) Return (MapW*MapH*z)+(y*MapW)+x End Function Function GetMapX(p) Return p Mod MapW End Function Function GetMapY(p) Return Floor((p Mod (MapW*MapH))/MapW) End Function Function GetMapZ(p) Return Floor(p /(MapW*MapH))+1 End Function |
| ||
| hmm.. And what if I say: "I don't know what the width will be, it's to be changed on the fly" ? |
| ||
| That wont work :P |
| ||
| Yeah, the WIDTH must be constant, unless you have some way of dynamically rewriting the expression at runtime ;) |
| ||
another way to minimize multiplications is to take any unnecessary multiplications out of the inner loop.
local array%[2048]
local save%[32,64]
width = 32
height = 64
local p%=0
for y = 0 until height
for x = 0 until Width
save[x,y] = array[p+x]
next
p:+width ' taking multiplication out increases speed significantly
next
|
| ||
| Optimising the integer multiplication is just so unnecessary it's just crazy. Write clean code, not 'fast' code, and profile, profile, profile. |
| ||
well then. Lookup isn't faster at all.. ._. Pity, but still not as bad as having to hide a giraffe in your bathroom!SuperStrict Local a1:Int[100] Local a2:Int[10,10] For Local y:Int=0 To 9 For Local x:Int=0 To 9 a2[x,y]=x+y*10 Next Next Local x:Int=3 Local y:Int=4 Local w:Int=10 Local old:Int=MilliSecs() For Local t:Int=0 To 499999999 a1[x+y*w] =t Next Print MilliSecs()-old old=MilliSecs() For Local t:Int=0 To 499999999 a1[ a2[x,y] ] =t Next Print MilliSecs()-old End |
| ||
| @Michael Reitzenstein you think it's crazy but when when you are working with pixmaps, of 1024 x 768, rgba, it makes a lot of difference no matter how you look at it. |
| ||
| If you go that nutty and do rt ops on that sized pixmaps, I would consider using shaders. Thats their field, not a CPUs job. |
| ||
| then again you are assuming there is only one purpose for manipulating pixmaps. I am shure you seen several post here (one discused by Gray Alien and others) where that is not the case. my purpose for manipulationg a pixmap that size is not as obvious. |
| ||
| I didn't assume any purpose actually. but in either case a shader is several magnitudes faster, does not mather what its purpose will be even if you use it to calculate a potential field to calculate ai movements in. Operation on 1D, 2D or 3D data -> GPU will outperform your system even if you have a dual core Operation on this kind of dataset is exactly the job of it. |
| ||
| well then I guess I don't understand shaders at all and I will need to look in to it, I will credit you for any lesson learned or will come and challenge you over it when I am ready. just a little question, I posted a demo code a while back: http://www.blitzmax.com/Community/posts.php?topic=63609#710366 do you think that can be made faster any other way, I have made it about 30% faster from what was posted by optimizing it. or how about this one: http://www.blitzmax.com/Community/posts.php?topic=73450#820844 if that is the case, well hell, I'll leave pixel bashing alone. |
| ||
| Hi Jesse, I just grabbed the source code you're pointing to, and it took me about twenty seconds to find this line: WritePixel(pix,xp+i,yp+j,textureimg[ttx21, tty21]) This is a completely unnecessary function call in your inner loop, because all WritePixel does is: Function WritePixel( pixmap:TPixmap,x,y,argb ) pixmap.WritePixel x,y,argb End Function And so no, it doesn't 'make a difference no matter which way you look at it', because your demo (pretty cool by the way) ran fine with this much more costly implementation detail. Instead of worrying about minor optimizations, profile the thing and find out what is REALLY slowing it down, because if you try to optimize without profiling you will be wrong, and just make your code ugly. |
| ||
By the way, since you asked for speedup tips, you can inline the code from the BlitzMax pixmap code if you know what the format is in advance. Write an inline of these:Method PixelPtr:Byte Ptr( x,y ) Return pixels+y*pitch+x*BytesPerPixel[format] End Method Method WritePixel( x,y,argb ) Assert x>=0 And x<width And y>=0 And y<height Else "Pixmap coordinates out of bounds" Local p:Byte Ptr=PixelPtr(x,y) Select format Case PF_A8 p[0]=argb Shr 24 Case PF_I8 p[0]=( (argb Shr 16 & $ff)+(argb Shr 8 & $ff)+(argb & $ff) )/3 Case PF_RGB888 p[0]=argb Shr 16 ; p[1]=argb Shr 8 ; p[2]=argb Case PF_BGR888 p[0]=argb ; p[1]=argb Shr 8 ; p[2]=argb Shr 16 Case PF_RGBA8888 p[0]=argb Shr 16 ; p[1]=argb Shr 8 ; p[2]=argb ; p[3]=argb Shr 24 Case PF_BGRA8888 p[0]=argb ; p[1]=argb Shr 8 ; p[2]=argb Shr 16 ; p[3]=argb Shr 24 End Select End Method Find the pixel offset by inlining pixelptr and use a format in your array such that you can cast the pixel pointer to an int ptr and assign straight over. Of course, this is the kind of optimisation that you'd make after 1) the program is too slow for your purposes and 2) after profiling it's clear that this is a speedup that'll give the highest return on investment |
| ||
| I never said that code was optimized. obviously I can do that and more. but I am more concerned about what Dreamora said about shaders and the like. if his method is faster why am I wasting my time with pixels. |
| ||
| If you know that you stay on a specific format of the above ones you can even opt it further by using memcopy instead of that many shifts and assignements. further opts would be by not using such commands at all but doing p :+ sizeofColor to go through => to get the maximum out of BM use the default commands and their implementation as an idea on how to optimize it seriously for your specific need. |
| ||
| I made an antialias pixmap rotation program a while back to practice on pixmap I know it's pointless when you have timage to work with and image rotation but yust to illustrate the fact that I done it before here it is: it is not the complete program just the main routine. [edited] wrong version |
| ||
| Jesse: No, but you said the integer multiply matters, but your code seems to run fine even though it's 100x more wasteful than an unnecessary multiply. If you don't know how to write shaders, you're in for a world of hurt. If that's worth it to speed up this effect (or you want to learn shaders for something else), then fine, but if you just want to speed this up then you can probably do it fine in software. Dreamora: Memcopy won't gain that code anything. It's not copying blocks around. And a) I didn't suggest using those commands, I suggested stripping out the necessary code from them, and b) no, p:+sizeofcolor will not work because with a pixmap, pitch doesn't necessarily equal width*BytesPerPixel[ format ]. If it did, the PixelPtr code would look like Return pixels + ( y * width + x ) * BytesPerPixel[ format ] Do you actually, you know, read the code before having an opinion? |
| ||
| I need to look into shaders maybe helpful for something else. replaced the above code with the right one. |
| ||
| Well, a color is a block as well. Write pixel assigns 4 bytes manually. Memcopy can assign them as one block or copy them in. But it was more a general hint when working with images or similar nicely aligned byte ptr structures, as memcopy allows you to copy around whole lines. It makes little point to copy each color component on its own if you just could copy them as whole. So yes I read what you wrote Michael. The memcopy for example will drastically speedup the write pixel end. but even more if you would write in more than 1 pixel like a part of a different pixmap or whatever. Something that needs a loop etc without memcopy. But: Not opting it now and profiling it when it is finished might be the much more worthfull approach. Reason is that there might be cross relations that you do not have in now but that could in the end have beneficial effects that you kill by "over optimizing" the code by now. There is nothing worse than "cool" programmers, that forget the global goal and performance due to their local detail working. |
| ||
| I also know there are "cool" programmers that spend their time criticising others while never actually helping solve problems. :) |
| ||
| A color is a block as well? Yes, a 32 bit one, for which there's an optimization on x86 that you might be familiar with. Memalloc() is 4 byte aligned - so cast the pointer to int, like I suggested many posts up: Find the pixel offset by inlining pixelptr and use a format in your array such that you can cast the pixel pointer to an int ptr and assign straight over. Which is why I believe you didn't read my post and/or the code. Memcopy will not speed ANYTHING up in Jesse's case. If you're talking about the general case, then sure, it's very very useful for copying blocks - just don't use it past the boundaries of a single line (there may or may not be empty space between them in a Blitz Pixmap). I agree 100% with the profile it sentiment (well, that's the reason I got involved in this thread in the first place). Jesse - Are you talking about me? Because I'm trying to give helpful advice here. Profile your code, find out what's slow, and fix that. It will never be what you expect. That's why I pointed out WritePixel in your inner loop, not to criticize, just to point out that it's easy to miss something that can make a big difference on even a small project. If you don't want to listen to that advice, fine, I don't really care. But trust me, it is a learning step most coders go through. Even Dreamora agrees! |
| ||
| of course I was not talking about you. but I assume dreamora was talking about me that is why I said that. |
| ||
| No, definitely not as you are asking intelligent questions and not just assuming that pushing in any available optimation will raise the end performance. It was more a general statement on what kind of "optimation attitude" you should avoid :) |
| ||
| Oh right, I see. Sorry I jumped to the wrong conclusion. Best of luck, anyway. |
   |