 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / August 2006Objects are slow ?
well i always read people writting about objects make software slow umm currently i ma having this problem i need to build a huge 2 dimention Array of an object this Object contain : int, int, boolean, boolean ; and since the array is huge we need the processes on the array be very fast so instead of doing it as one 2dimention array of that object i do 4 2dimention arrays int, int , boolean, boolean and do the process on them will that be faster ??? > i need to build a huge 2 dimention Array of an object > [quoted text clipped - 12 lines] > > will that be faster ??? It will almost definitely be slower. Java doesn't really have two-dimensional arrays. Instead it has arrays of arrays. So instead of having around n objects, for huge n, you now have 2n small arrays. Not so good. If you want to compact you data, use large single dimension arrays. And profile your application of course. Tom Hawtin >> so instead of doing it as one 2dimention array of that object >> >> i do 4 2dimention arrays int, int , boolean, boolean >> and do the process on them > of arrays. So instead of having around n objects, for huge n, you now > have 2n small arrays. Not so good. Oops. 2D array of objects vs multiple 2D arrays of primitives. Still, if I was going for compactness, I'd go for multiple 1D arrays (or probably 1 1D array). Tom Hawtin > well i always read people writting about objects make software slow Using objects wont impact the speed - that argument is a red herring for your problem. > umm currently i ma having this problem > [quoted text clipped - 14 lines] > > will that be faster ??? Q) how long is a piece of string? A) Measure it and you will find out. Other than that, do consider that depending upon what you want to do with the collection once its populated, different types of collections can give you better performance. >> well i always read people writting about objects make software slow > > Using objects wont impact the speed - that argument is a red herring for > your problem. Not necessarily. The overhead for the object, object alignment, and references will add a few bytes per element. Considering that the payload is only 10 bytes, that may be a significant cost in cache space and memory access bandwidth. >> umm currently i ma having this problem >> [quoted text clipped - 22 lines] > with the collection once its populated, different types of collections > can give you better performance. The most important step at this point is to isolate the structure in its own class. That way, it will be possible to experiment with alternative designs, without rewriting the whole program. Patricia >>> well i always read people writting about objects make software slow >> [quoted text clipped - 5 lines] > payload is only 10 bytes, that may be a significant cost in cache space > and memory access bandwidth. True, but such micro optimizations are rarely useful. Performance problems are typically in other areas. The only true way to find out is to measure. >>> umm currently i ma having this problem >>> [quoted text clipped - 26 lines] > own class. That way, it will be possible to experiment with alternative > designs, without rewriting the whole program. Agreed, and once you have a dataholder for the 4 values, it can be used within different collections to see which is appropriate. > Patricia >>>> well i always read people writting about objects make software slow >>> [quoted text clipped - 8 lines] > True, but such micro optimizations are rarely useful. Performance > problems are typically in other areas. It depends. I've done enough work with large arrays, especially in Fortran, that I've seen situations in which micro-optimization changed a three day job to a few hours. If 99.9% of the time in the unoptimized program really is in a few array tasks, optimizing array access does matter. > The only true way to find out is to measure. Absolutely, totally agree. >>>> umm currently i ma having this problem >>>> [quoted text clipped - 29 lines] > Agreed, and once you have a dataholder for the 4 values, it can be used > within different collections to see which is appropriate. I would not even externalize the idea of the 4 value data holder. It may be that there are a significant number of operations that need to work along a particular dimension of the first int array. In that case, four primitive arrays may be most efficient. Patricia >>>>> well i always read people writting about objects make software slow >>>> [quoted text clipped - 15 lines] >If 99.9% of the time in the unoptimized program really is in a few array >tasks, optimizing array access does matter. Seconded. It can indeed make a huge difference. The real issue, as I understand it, is making effective use of cache, and a program that accesses memory words in contiguous order (rather than jumping around) is likely to do better there. The example that's commonly used in other languages (Patricia, you almost surely know this, but the OP might not) is a nested loop over a 2D array; typically one way of nesting the loops gives much much better performance than the other. Seems to work that way in Java too, based on a quick experiment. (Exactly how much almost surely depends on the details of the system, but my little test program showed performance differences of over an order of magnitude. !) [ snip ] >I would not even externalize the idea of the 4 value data holder. > >It may be that there are a significant number of operations that need to >work along a particular dimension of the first int array. In that case, >four primitive arrays may be most efficient. Agreed. It might not be as pretty as an array of objects, but your suggestion to hide the details in a way that makes it easy to change them may help with that.  SignatureB. L. Massingill ObDisclaimer: I don't speak for my employers; they return the favor. >>>>> well i always read people writting about objects make software slow >>>> [quoted text clipped - 12 lines] > Fortran, that I've seen situations in which micro-optimization changed a > three day job to a few hours. Sure, me too (coming from a background of real-time application and embedded apps), but I measure the program first, then I perform what might initially appear to be the micro-optimization. AndrewMcDonagh wrote On 08/03/06 18:01,: > Sure, me too (coming from a background of real-time application and > embedded apps), but I measure the program first, then I perform what > might initially appear to be the micro-optimization. Let's spend a few moments estimating how "micro" the optimization is. To summarize the O.P., there's a "huge" array (apparently two-dimensional) of objects each with a payload of two ints and two booleans. The O.P. wonders whether he'd be better off using four parallel arrays of primitives. That's not much information to go on, so we'll need to augment it with some assumptions. I'll assume - The arrays are [N][N] in size, where N is sufficiently large for N*N to be called "huge." - An instance of the O.P.'s object occupies 24 bytes: ten bytes of payload plus eight bytes of bookkeeping used by the JVM, rounded up to a multiple of eight. - An array occupies 16 bytes plus the space for its payload elements: an array is an object and thus has the JVM bookkeeping, and an array also probably has some bookkeeping of its own (e.g., its length is probably stored somewhere). - An object reference occupies four bytes. The latter three assumptions obviously depend on the JVM and will vary from one to another; if you've got more specific information about the O.P.'s JVM, by all means use it. With these assumptions, the SomeClass[N][N] approach uses - 24*N*N bytes for the SomeClass object instances, plus - N*(4*N+16) bytes for N one-dimensional arrays containing N SomeClass references apiece, plus - 4*N+16 bytes for one one-dimensional array containing N references to the other arrays. Grand total for SomeClass[N][N]: 28*N*N + 20*N + 16 bytes. The alternative of two int[N][N] arrays and two boolean[N][N] arrays uses - 2*N*(4*N+16) bytes for two sets of N int[N] arrays, plus - 2*(4*N+16) bytes for two N-element arrays containing references to the int[N] arrays, plus - 2*N*(N+16) bytes for two sets of N boolean[N] arrays, plus - 2*(4*N+16) bytes for two N-element arrays containing references to the boolean[N] arrays. Grand total for parallel arrays: 10*N*N + 80*N + 32 bytes. Memory saved by using parallel arrays: 18*N*N - 60*N - 16 bytes -- roughly speaking, 18*"huge" bytes. A savings of 18*"huge" bytes isn't a "micro"-optimization. This isn't to say that the optimization *should* be done, of course. But the size of the potential savings is large enough to influence the design from the outset: You might decide to start with SomeClass[N][N], but if you think you may want to change to parallel arrays or to a single long[N][N] or even to a byte[HUGE], you won't let those SomeClass objects escape "into the wild." You'll hide them behind accessors so you can change representations easily if it proves necessary. This is the sort of choice that's easy to make before coding, much harder to make after the code is deployed and found to be performing poorly. SignatureEric.Sosman@sun.com ... > Memory saved by using parallel arrays: 18*N*N - 60*N - 16 > bytes -- roughly speaking, 18*"huge" bytes. A savings of > 18*"huge" bytes isn't a "micro"-optimization. Note, also, where those bytes are. The 8 bytes per object overhead, and the padding to bring the object size up to a multiple of 8 bytes are likely to be interleaved with payload data. They will occupy cache space and use memory bandwidth, much more expensive than the same overhead in a separate structure. > This isn't to say that the optimization *should* be done, > of course. But the size of the potential savings is large [quoted text clipped - 7 lines] > much harder to make after the code is deployed and found to > be performing poorly. Completely agree. Patricia > ... >> Memory saved by using parallel arrays: 18*N*N - 60*N - 16 [quoted text clipped - 20 lines] > > Completely agree. I completely agree...unless the usage of the array is a one time occurrence and the real bottle neck in the system is a simple loop somewhere that gets executed continually, which really should be a hash table lookup. Measure to find the problem area - dont guess. > Patricia AndrewMcDonagh wrote On 08/04/06 18:12,: >>... >> [quoted text clipped - 18 lines] > > Measure to find the problem area - dont guess. Do both: Guess *and* measure. Guess beforehand, to inform your design. Measure afterwards, to confirm (or refute) the guesswork and to refine the implementation. Recommended reading: "Programming Pearls" by Jon Bentley. SignatureEric.Sosman@sun.com > > Measure to find the problem area - dont guess. > > Do both: Guess *and* measure. Guess beforehand, to inform > your design. Measure afterwards, to confirm (or refute) the > guesswork and to refine the implementation. ... and to refine your intuition and understanding of performance issues. That intuition is a valuable asset, don't let it go stale, or your initial designs will more frequently require modification after you have measured. At that time you have necessarily invested a fair bit of time in implementing something which you may discover has to be changed in ways you didn't anticipate. A well-trained intuition will help you avoid such situations. -- chris Chris Uppal skrev: > ... and to refine your intuition and understanding of performance issues. > > That intuition is a valuable asset, don't let it go stale ... Completely OT here. Really. Completely. I recently had a conversation about computer intuition, and concluded that it's an oxymoron. Intuition is about forming thoughts on first experiences; in humans, these are exclusively genetic in nature, for example, someone wrote somewhere that humans are genetically predisposed to fear only three things: spiders, loud noises and something else that I can't remember just now (probably deadlines). So if you show a spider to a three-year-old, it will probably become upset (the three-year-old, that is). If you show a three-year-old the source code for a poorly-performing java application, it's unlikely that that three-year-old will start crying (unless, of course, you're using generics, whose angle-brackets strikes ancient fear into all rational beings). In order to have any intuition about computers, we must evolve responses to them, which means that humans and machines must cohabit for millions of years. Which we haven't. Yet. So, being extraordinarily anal, I propose that no one, yet, has any intuition about java performance; many have extrapolatable experience, but not intuition. However, now I've taken a peak at a dictionary and seen the definition: in·tu·i·tion Audio pronunciation of "intuition" ( P ) Pronunciation Key (nt-shn, -ty-) n. 1. 1. The act or faculty of knowing or sensing without the use of rational processes; immediate cognition. See Synonyms at reason. 2. Knowledge gained by the use of this faculty; a perceptive insight. 2. A sense of something not evident or deducible; an impression. 1.2 seems to suggest that I'm completely wrong. Oh, well. I would also like to point out that I've just painted my kitchen a colour formally known as, "Apple cider 3," but there's a haunting suspicion among my friends that it's really just plain-ol' cream. .ed -- www.edmundkirwan.com - Home of the Fractal Class Composition ... > In order to have any intuition about computers, we must evolve > responses to them, which means that humans and machines must cohabit > for millions of years. I would agree with this if you had said "instinct" not "intuition". > So, being extraordinarily anal, I propose that no one, yet, has any > intuition about java performance; many have extrapolatable experience, [quoted text clipped - 13 lines] > > 1.2 seems to suggest that I'm completely wrong. That is what I thought intuition meant. Instinct must be inherited, but intuition can come from anywhere other than fully thought out chains of logic, including experience. I would agree that, at least in the technical sense, we don't have instincts about Java performance. We can have intuition. Patricia thank you very much all of you i got lots of information of your replays thanks really a lot > In order to have any intuition about computers, we must evolve > responses to them, which means that humans and machines must cohabit > for millions of years. Like Patricia, I believe you are thinking of instict here. Intuition is something different. BTW, I think we have instinctive aversion to/distrust of more than just 3 things -- heights, snakes, and sudden movement come to mind in adition to splders, deadlines, and hard rock. > I would also like to point out that I've just painted my kitchen a > colour formally known as, "Apple cider 3," but there's a haunting > suspicion among my friends that it's really just plain-ol' cream. An ex-collegue of mine would have described it as "white, with a hint of marketing" ;-) -- chris > Memory saved by using parallel arrays: 18*N*N - 60*N - 16 > bytes -- roughly speaking, 18*"huge" bytes. A savings of > 18*"huge" bytes isn't a "micro"-optimization. http://www.azulsystems.com/ > well i always read people writting about objects make software slow > [quoted text clipped - 16 lines] > > will that be faster ??? As per Thomas's comments, it'll most likely be slower for these reasons: 1. Proximity: the four data types are going to be in the same frame of reference with the Object, but with four arrays they may be outside of the processor's cache. 2. Array seek penalty: you're retrieving the Object but once (if you don't program it in, the JIT will likely do it for you anyways), so you get one array seek penalty instead of for (actually two instead of eight...). But the fastest way is going to be to turn it all into one 1D array because you get 1 seek penalty and 1 reference resolution... > well i always read people writting about objects make software slow > [quoted text clipped - 16 lines] > > will that be faster ??? Nobody knows what will be faster until someone measures and compares all options. A first tip, mentioned by others already is to not use multidimensional arrays, but instead use singledimensional arrays and do your own index calculations. Multidimensional arrays in java are practically unusable for any performance intensive task. As to whether one vs. many arrays is better, that is truly impossible to answer without knowing your data. It depends a lot on how you access the data. If you usually access only one field from many objects at a time, multiple arrays may be more efficient, but if you usually access one whole object at a time, a single array is likely to work better. As a totally different solution, I'll give a slightly eccentric suggestion. Store everything into a single int[] array, using the values 0 and 1 to represent boolean false and true, respectively. If you need to convert the last two ints back to booleans, use something like boolean b = integer & 1 == 0 ? 0 : 1. If the JIT optimizer has any brains, this operation will be compiled to something very simple (probably integer & 1). This adds a 6 byte overhead to each object [*] , but this solution has optimal memory locality and alignment on most platforms, if we assume you are going to access a whole object at a time. But, alas, this is very ugly ;-) As always, you /must/ benchmark any solutions before you can draw any definitive conclusions. Regards, Daniel Sjöblom * But don't forget, if you were using object references the overhead would be even higher per object ... > As a totally different solution, I'll give a slightly eccentric > suggestion. Store everything into a single int[] array, using the [quoted text clipped - 6 lines] > platforms, if we assume you are going to access a whole object at a > time. But, alas, this is very ugly ;-) I would be very concerned about the wasted space when doing this for a large, frequently accessed array. All data is going to be aligned anyway, in the sense that no field will cross a word or cache line boundary, the alignment question that actually affects performance. Modern processors can pull a single byte from a word very fast, so I would not worry about that. The real problem with large, frequently accessed arrays is getting the data to where it needs to be. The objective should be to make the best possible use of every scrap of memory bandwidth and cache space. Depending on how the data is accessed, the fastest might be a linear array for each field, so that each array can be dense. However, until the program has been written and can be measured, the design objective should be to avoid precluding any of these solutions. That means minimizing the amount of code that knows how the data is arranged in memory. Patricia > ... > > As a totally different solution, I'll give a slightly eccentric [quoted text clipped - 15 lines] > actually affects performance. Modern processors can pull a single byte > from a word very fast, so I would not worry about that. True, although I did have a couple of other things in mind: I was thinking of the fact that if the data is packed as tight as possible, say into a byte array, then the 32-bit values would be on 2 byte boundaries, which is not optimal. But this consideration is moot anyway in java, since you can't read integers directly from byte arrays like you can in other languages. The other thing is that this way every object is 16 bytes, probably aligned at 16 byte boundaries (assuming the VM allocates large objects at page boundaries.) This is optimal for vectorization on many processors, although this may just be wishful thinking, I don't know how good typical VMs are at vectorizing array accesses. > The real problem with large, frequently accessed arrays is getting the > data to where it needs to be. The objective should be to make the best [quoted text clipped - 7 lines] > That means minimizing the amount of code that knows how the data is > arranged in memory. Agreed. It would be insane to not wrap this in some implementation independent interface. Regards, Daniel Sjöblom > If you usually access only one field from many objects at a > time, multiple arrays may be more efficient, but if you usually access > one whole object at a time, a single array is likely to work better. Not necessarily even then. For instance if you have an array of objects which you access sequentially, then depending on your luck the resulting access pattern to real memory may not be very linear -- it depends on where the object are placed (which in turn depends on when they were created and their history since). If you stored the same data in N arrays of primitives, then the access to each array would be linear (assuming a JVM implementation which is not actually insane ;-). And memory subsystems /like/ linear access... -- chris > > If you usually access only one field from many objects at a > > time, multiple arrays may be more efficient, but if you usually access [quoted text clipped - 5 lines] > are placed (which in turn depends on when they were created and their history > since). Yes. This is why I suggested the offbeat solution of using a single int array for storing the objects, because java doesn't support value objects. > If you stored the same data in N arrays of primitives, then the access > to each array would be linear (assuming a JVM implementation which is not > actually insane ;-). And memory subsystems /like/ linear access... All true :-) Regards, Daniel Sjöblom > As a totally different solution, I'll give a slightly eccentric > suggestion. Store everything into a single int[] array, using the > values 0 and 1 to represent boolean false and true, respectively. If > you need to convert the last two ints back to booleans, use something > like boolean b = integer & 1 == 0 ? 0 : 1. That should read 'boolean b = integer & 1 != 0', which actually compiles ;-) I was thinking more about how the bytecode looks when I wrote the above line. Daniel Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.