BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Delphi 3: Efficient squareroot computation/How to use SSE co Goto page 1, 2  Next          BorlandTalk.com Forum Index -> Delphi Language BASM View previous topic :: View next topic   Author Message Francesco Ferrucci Guest Posted: Sun Oct 16, 2005 2:18 pm    Post subject: Delphi 3: Efficient squareroot computation/How to use SSE co Hello everybody, I have found on the net an efficient implementation of calculating an approximation of the squareroot. It uses SSE commands. I am using Delphi 3 and the asm compiler says that it does not recognize these commands (of course, those days SSE was not known yet :-) Question: Is there a way to use these commands anyway? Or is there a similar efficient implementation available for Delphi? The specific piece of code is (in C++): __asm { rsqrtss xmm0, x rcpss xmm0, xmm0 movss x, xmm0 }; Many thanks in advance. Best regards, Francesco Back to top Avatar Zondertau Guest Posted: Sun Oct 16, 2005 3:11 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Quote: I have found on the net an efficient implementation of calculating an approximation of the squareroot. It uses SSE commands. I am using Delphi 3 and the asm compiler says that it does not recognize these commands (of course, those days SSE was not known yet :-) Question: Is there a way to use these commands anyway? Or is there a similar efficient implementation available for Delphi? The specific piece of code is (in C++): __asm { rsqrtss xmm0, x rcpss xmm0, xmm0 movss x, xmm0 }; This code first computes the reprocicals of the suare root of X and then the reprocical of the result. Why are you doing this double work. ISTM both speed and accuracy will be better if you simply use the SQRTSS instruction. This can be coded in Delphi 3 (i assume it does support inline asm) using DB directives. This allows you to insert literal bytes into the compiled codes. However for us to be able to meaningfully translate this in DB's we would need to know the address of the variable X. It would be useful if you posted the code that is supposed to use the square root calculation. This way we could determine the best way to optimize it. Back to top Max Guest Posted: Sun Oct 16, 2005 4:56 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS A topic for Fastcode? Back to top Francesco Ferrucci Guest Posted: Sun Oct 16, 2005 5:01 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Avatar, thanks for your quick reply! You are right, the mentioned method is not as precise as using the SQRTSS command, but coded in C++ it is about five times faster on my machine than SQRTSS (Pentium M Sonoma). Of course, SQRTSS is more than twice as fast as the standard C++ sqrt function. Yes, Delphi 3 supports inline asm. The idea with DB directives is great, I did not know this possibility until now. I want to use the fast squareroot computation to implement an effective version of the A* shortest path computation in a road network while using the air distance of the current point and the target point as heuristic bound. The coordinates of the both points are delivered to the method as parameters. So here's the important method: function TWayDlg.aStarValue(x1,y1,x2,y2:Double):LongInt; var diffX, diffY:Double; begin diffX := x1 - x2; diffY := y1 - y2; aStarValue := ceil(sqrt(diffX * diffX + diffY * diffY) * 1000); end; The multiplication by 1000 is done because the values are quite big and cause an integer overflow. So I divided them before multiplying. If you have a better idea doing this I would appreciate it. I hope this is the information that you asked for. Thank you very much for your help. Best regards, Francesco "Avatar Zondertau" <avatarzt (AT) gmail (DOT) com (please reply to newsgroup)> schrieb im Newsbeitrag news:43526db8 (AT) newsgroups (DOT) borland.com... Quote: I have found on the net an efficient implementation of calculating an approximation of the squareroot. It uses SSE commands. I am using Delphi 3 and the asm compiler says that it does not recognize these commands (of course, those days SSE was not known yet :-) Question: Is there a way to use these commands anyway? Or is there a similar efficient implementation available for Delphi? The specific piece of code is (in C++): __asm { rsqrtss xmm0, x rcpss xmm0, xmm0 movss x, xmm0 }; This code first computes the reprocicals of the suare root of X and then the reprocical of the result. Why are you doing this double work. ISTM both speed and accuracy will be better if you simply use the SQRTSS instruction. This can be coded in Delphi 3 (i assume it does support inline asm) using DB directives. This allows you to insert literal bytes into the compiled codes. However for us to be able to meaningfully translate this in DB's we would need to know the address of the variable X. It would be useful if you posted the code that is supposed to use the square root calculation. This way we could determine the best way to optimize it. Back to top John O'Harrow Guest Posted: Sun Oct 16, 2005 5:23 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS "Francesco Ferrucci" <ferrucci (AT) web (DOT) de> wrote Quote: The multiplication by 1000 is done because the values are quite big and cause an integer overflow. >So I divided them before multiplying. If you have a better idea doing this I would appreciate it. I >hope this is the information that you asked for. If the multiplication and Division by 1000 are purely to prevent overflows as you suggest, you will probably gain greatly by using 1024 instead of 1000. The compiler will then replace the multiply/divide by shift commands, which will be much faster regards, John Back to top Avatar Zondertau Guest Posted: Sun Oct 16, 2005 5:23 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Quote: Avatar, thanks for your quick reply! You are right, the mentioned method is not as precise as using the SQRTSS command, but coded in C++ it is about five times faster on my machine than SQRTSS (Pentium M Sonoma). Of course, SQRTSS is more than twice as fast as the standard C++ sqrt function. Yes, Delphi 3 supports inline asm. The idea with DB directives is great, I did not know this possibility until now. I want to use the fast squareroot computation to implement an effective version of the A* shortest path computation in a road network while using the air distance of the current point and the target point as heuristic bound. The coordinates of the both points are delivered to the method as parameters. So here's the important method: The best solution would be to code this entire function in ASM, using SSE for the subtract and multiplication operations as well. Before this can be coded the signature of the function should be claer. There are several modifications which would allow faster implementations: - Using Single instead of Double parameters - Making the parameters const - Making this a standalone funciton instead of a method Another thing that is relevant: do you want to use only original SSE instructions or is SSE2 also OK? SSE2 allows operations on Doubles, which would allow a faster implementation if the function really must accept doubles. Back to top Anders Isaksson Guest Posted: Sun Oct 16, 2005 5:54 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Francesco Ferrucci wrote: Quote: I want to use the fast squareroot computation to implement an effective version of the A* shortest path computation in a road network while using the air distance of the current point and the target point as heuristic bound. The coordinates of the both points are delivered to the method as parameters. So here's the important method: function TWayDlg.aStarValue(x1,y1,x2,y2:Double):LongInt; var diffX, diffY:Double; begin diffX := x1 - x2; diffY := y1 - y2; aStarValue := ceil(sqrt(diffX * diffX + diffY * diffY) * 1000); end; Two questions about the algorithm (as I don't have the big picture): Why do you need to take the square root? If the results are only compared to other results from the same routine, there's no need to actually compute the square root. The relation (less, equal, greater) will remain the same. Why do you have to use integer? It would probably be faster with doubles all over, as you don't have to do any scaling and ceil() at all. -- Anders Isaksson, Sweden BlockCAD: http://web.telia.com/~u16122508/proglego.htm Gallery: http://web.telia.com/~u16122508/gallery/index.htm Back to top Francesco Ferrucci Guest Posted: Sun Oct 16, 2005 6:09 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Quote: The best solution would be to code this entire function in ASM, using SSE for the subtract and multiplication operations as well. Before this can be coded the signature of the function should be claer. There are several modifications which would allow faster implementations: - Using Single instead of Double parameters - Making the parameters const - Making this a standalone funciton instead of a method Another thing that is relevant: do you want to use only original SSE instructions or is SSE2 also OK? SSE2 allows operations on Doubles, which would allow a faster implementation if the function really must accept doubles. As the values are quite big, single would not be big enough. But originally the x1, y1, x2 and y2 coordinates are integer numbers - the only problem is the (temporal) integer overflow when multiplying before taking the square root... If it would be possible to use 64bit integers, then there is no need to use double for the parameters at all. Also the result can be ceiled to an integer, that's no problem. The parameters can be const and the use of SSE2 is also no problem. I don't know exactly what the difference is between a standalone function and a method. Regards, Francesco Back to top Francesco Ferrucci Guest Posted: Sun Oct 16, 2005 6:18 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Quote: Two questions about the algorithm (as I don't have the big picture): Why do you need to take the square root? If the results are only compared to other results from the same routine, there's no need to actually compute the square root. The relation (less, equal, greater) will remain the same. Why do you have to use integer? It would probably be faster with doubles all over, as you don't have to do any scaling and ceil() at all. 1. The result is added to another value. But yes, it could be possible to square the other value to which this value shall be added instead of squarerooting this value. But then the values could get easily bigger than a 32bit integer. Would you recommend the use of a double value, then? 2. Using doubles for all values is also fine. But because the original values are integer, it would also be possible to use only integers (if 64bit integers are available in the multiplication step with ceiling after calculating the squareroot). Regards, Francesco Back to top Anders Isaksson Guest Posted: Sun Oct 16, 2005 8:14 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Francesco Ferrucci wrote: Quote: Would you recommend the use of a double value, then? If it's not a horrendous lot of work, I think it would be worth a try. Depends a lot on what you do with the numbers, how exact they have to be, what operations you do on them etc. etc. For example, int64 division is really sloooow in older versions of Delphi (I think D2005 is better, not sure about D7). In my D5, the fastest way to do an int64 divide in plain Pascal is to convert to double, do a floating division and convert back to int64. Naturally, that sequence is much faster if everything is a double to begin with... As for your algorithm, I think getting rid of the square roots would give a great benefit, doing one (or at least just a small number of) squares instead seems like a small price. But I'm only guessing, of course, as I don't know all about your code :-) -- Anders Isaksson, Sweden BlockCAD: http://web.telia.com/~u16122508/proglego.htm Gallery: http://web.telia.com/~u16122508/gallery/index.htm Back to top Francesco Ferrucci Guest Posted: Sun Oct 16, 2005 9:16 pm    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Hello Anders, Quote: Francesco Ferrucci wrote: Would you recommend the use of a double value, then? If it's not a horrendous lot of work, I think it would be worth a try. Depends a lot on what you do with the numbers, how exact they have to be, what operations you do on them etc. etc. For example, int64 division is really sloooow in older versions of Delphi (I think D2005 is better, not sure about D7). In my D5, the fastest way to do an int64 divide in plain Pascal is to convert to double, do a floating division and convert back to int64. Naturally, that sequence is much faster if everything is a double to begin with... As for your algorithm, I think getting rid of the square roots would give a great benefit, doing one (or at least just a small number of) squares instead seems like a small price. But I'm only guessing, of course, as I don't know all about your code I thought again about the idea with squaring the other part. It does not work because squaring the other part and adding it to the square does not give the same result because it neglects the first binomial formula. So I think I need an efficient squareroot implementation. Nevertheless thanks for your idea! Regards, Francesco Back to top Adem Guest Posted: Mon Oct 17, 2005 2:48 am    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Francesco Ferrucci wrote: Quote: I have found on the net an efficient implementation of calculating an approximation of the squareroot. It uses SSE commands. I am using Delphi 3 and the asm compiler says that it does not recognize these commands (of course, those days SSE was not known yet For A* you should not need exact values, you should not even need to calculate sqrt. First, if you can spare some RAM, you can look at this with a bit of lateral thinking. I'd tackle the problem this way: Determine a *square* of upper limit for the distance that you would consider 'too far'. if 100 is your upper limit, then your TOO_FAR limit would be 10,000. i.e. const TOO_FAR = 10000; SqDistance[0..TOO_FAR] of Double; {on integer or whatever} Then, construct a static array and fill each cell with the sqare root of its index. It is best, that you have this as an .inc file to your project. While the .inc file will look big, the actual memory footprint of this example will be around 80 K when the cells are Double. Anyway, the SqDistance array should contain this sort of thing: SqDistance: Array [0..TOO_FAR] of Single = ( 0, 1, 1.414213562, {sqrt(2)} 1.732050808, {sqrt(3)} 2, .... 99.96499387, 99.9699955, 99.97499687, 99.979998, 99.98499887, 99.9899995, 99.99499987, 100 ); now, your code looks like this function TWayDlg.aStarValue(x1,y1,x2,y2:Double):LongInt; var diffX:Double; diffY:Double; Index: Double; begin Result := -1; diffX := x1 - x2; diffY := y1 - y2; Index := diffX * diffX + diffY * diffY; if Index <= MAX_UPPER_VALUE then Result := SqDistance[ceil(Index)]; end; [This has only been compiled with notepad.exe ] It should be faster. You may have to scale up/down Index for better granularity. Once you get it right, gurus here are likely to rocketize your version through the magic of ASM. Till then HTH, Cheers, Adem Back to top Adem Guest Posted: Mon Oct 17, 2005 3:15 am    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Adem wrote: Quote: First, if you can spare some RAM, you can look at this with a bit of lateral thinking. I'd tackle the problem this way: What was I thinking? I wasted so much time writing the previous post.. There is a much simpler way --if all you are doing is to comparing line distances to points, you don't need any stinking <g> sqrt() calculations at all.. Just compare the 'diffX * diffX + diffY * diffY' value for each line. so, function TWayDlg.aStarValue(x1,y1,x2,y2:Double):LongInt; var diffX, diffY:Double; begin diffX := x1 - x2; diffY := y1 - y2; aStarValue := ceil(diffX * diffX + diffY * diffY); end; should be good and fast enough. Back to top Will DeWitt Jr. Guest Posted: Mon Oct 17, 2005 3:33 am    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Francesco Ferrucci wrote: Quote: I don't know exactly what the difference is between a standalone function and a method. A standalone function is something like this-- function Foo(const Value: integer): integer; A method is a function or procedure that is part of a class-- function TBar.Foo(const Value: integer): integer; Conceptually they're identical for the most part, but behind the scenes there are some subtle differences. In this case, I believe the difference Avatar is concerned about is the passing of "Self" to methods (which is a waste since "Self" won't be used). As a standalone function "Self" isn't passed, so it saves an instruction whenever the standalone function is called. For example, when the compiler calls TBar.Foo it generates code like this-- MOV EAX, Self MOV EDX, Value CALL TBar.Foo But when the compiler calls Foo (the standalone function), it only generates this-- MOV EAX, Value CALL TBar.Foo Will -- Want native support in Delphi for AMD64/EM64T? Vote here-- http://qc.borland.com/wc/qcmain.aspx?d=7324 Back to top Will DeWitt Jr. Guest Posted: Mon Oct 17, 2005 3:36 am    Post subject: Re: Delphi 3: Efficient squareroot computation/How to use SS Anders Isaksson wrote: Quote: For example, int64 division is really sloooow in older versions of Delphi Just for Francesco's sake: there's no Int64 support in Delphi 3 (it wasn't added until Delphi 4 AFAIK). If you want to work with 64-bit integers in D3 you'll end up rolling your own routines most likely. :( Will -- Want native support in Delphi for AMD64/EM64T? Vote here-- http://qc.borland.com/wc/qcmain.aspx?d=7324 Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> Delphi Language BASM All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  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 Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.