Aug 11
2008

Vector Operations

Posted by Walter Bright in Untagged 

WalterBright

Vector operations are when an operation is applied to each element of an array, and each operation is independent of the other elements of the array. For example, taking an array and multiplying each element by a constant, is typically expressed as a loop:

    for (int i = 0; i < array.length; i++)
         a[i] *= 4;

A more complex vector might be to add and scale:

    for (int i = 0; i < array.length; i++)
          a[i] = b[i] + c[i] * scale;

Since these are such common operations, in order to speed them up many computers added support for vector operations, so that multiple operations can be done in parallel (such as AMD and Intel's SIMD instructions). The trouble was that the loops specify the operations sequentially, one at a time.

This led to the development of auto-vectorizing compilers, which would recognize such loops, transform them internally into a higher level construct, then compile that construct down into vector machine code. Puzzlingly, the languages themselves rarely took the next logical step and provided a syntax to directly express a vector operation.

The irony is that the programmer must specify the vector operation in a low level manner, which the compiler transforms into a high level construct, which is then translated back down into low level code. It's like writing assembler code which the compiler transforms into C code and then compiles the C code. Why not write the C code directly?

The D programming language has done just that, providing a syntax to specify vector operations directly (without loops). The previous two examples would look like:

    a[ ] *= 4;

and:

    a[ ] = b[ ] + c[ ] * scale;

Here the [ ] notation means "the elements of the array", signaling a vector operation. An optional check is inserted to ensure that the arrays are all the same length, and a[] does not overlap b[ ] or c[ ].

The compiler has many ways it can implement this. The Digital Mars D compiler does it by converting it to a function call, one function for each combination of arguments and types. The most common cases of such functions get a hand-coded assembler implementation, the rest get a custom function generated by the compiler. This method was chosen for its easy adaptability to different architectures, as it doesn't require altering the code generator. There's certainly plenty of room for competing D implementations to aggressively pursue better optimization for these.

The advantages of vector operation syntax for the programmer are:

  • It succinctly and intuitively expresses the intent, which usually means faster programming and less buggy programs.
  • Auto vectorizing compilers are complex and tricky to build, and so most compilers aren't. With vector operations expressible in the language, the hard part is done already.
  • Even for relatively unsophisticated compilers, programmers can expect them to take advantage of any vector abilities of the target computer.
  • There becomes less need to buy expensive third party libraries just to speed up vector operations.
  • It encourages healthy competition among compiler vendors for doing a better job of compiling the vector operations, all to the benefit of the programmer.

At one point I investigated having vector operations be part of a user supplied library, but as Eric Niebler correctly pointed out to me, since arrays are a built-in first class type for D, then array operations must be as well.


Note: the gnu C compiler has, as a compiler extension, a syntax for vector operations. But I'm not aware of any momentum behind adding it to the future C or C++ language standards.



Comments (6)Add Comment
testing comments
written by rick luhmann, August 12, 2008
a test comment from me smilies/wink.gif
Some Historical Perspective
written by William Cohagan, August 15, 2008
Both Texas Instruments and CDC built/sold vector machines back in the 1970s. TI's ASC had a vectorizing Fortran compiler as well as language extensions (Array Cross Sections and SubArrays) to support vector operations. One difficulty with the latter approach is that it is possible to express a "vector operation" that in fact cannot be done on vector hardware due to (for instance) recursion. Obviously this depends on the particular semantics of the vector notation supported. The TI compiler actually did expand vector notation back into iterative code that was then analyzed/optimized by the vectorizer. It did a very good job (if I do say so myself!)

I believe the CDC Star compiler also supported vector notation.

Of course, predating all of this was Iverson's APL language (late 1950's?) Now *there* was a vector language!
APL , now there IS a vector language .
written by Bob Armstrong, August 26, 2008
It continues to surprise me to see people reinventing 30 and 40 year old wisdom . APLs and their progeny run some of the largest and most complex financial applications around the planet . For nearly 2 generations APLers have simply written ( in Arthur Whitney's K variant )

a : n # 4

to create a vector of n 4s .

Adding and scaling would be written just

a : scale * b + c

the order reversed because APLs read to the end of a sentence then synthesize the result working from that end .

But the APL statement is much stronger than simply operating on vectors . scale , b and c can be any dimensional arrays so long as meeting straight forward conformability rules .

In the still far from prime time APL informed language I'm constructing in free and open Forth , all indexing is modulo . So all arrays are conformable . Think trees , or better , bushes .

a b +

will add any two tree like numerical structures repeating elements of shorter branches to match the length of the longer .

But even this has not touched on APL's notions of operators which "map" functions over and between data sets in various commonly occurring patterns .

I'm not sure who the audience for D is , but it's unlikely to convert any APLers .


R is a vectorized language
written by jim holtman, August 26, 2008
If you want a vectorized language, try R. You can write:

a = b + c * scale

and the operation will be carried out on every element in the vectors
In XL, such operations can be redefined
written by Christophe de de Dinechin, August 28, 2008
XL has what I called "expression reduction" so that you can redefine such operations the way you want. For example, the generic scale example would be written:

function scale(A, B, C : vector) return vector written A*B+C is
for I in vector.range loop
result := A*B + C

You can then use it using as:

V : vector := V1 * V2 + V3

If the particular machine has actual vector operations, you could use them in the code as an optimization. Alternatively, you can "bytecode" the whole function, e.g.

function scale(A, B, C : vector) return vector written A*B+C is XL.BYTECODE.vec_scale

This also works for matrices, where the A*B+C operation doesn't mean the same thing as for vector because the same position in the matrix is not used for A and B. Having a way to create a "super-operator" combining the multiplication and addition improves things like memory locality a lot. How would D deal with the matrix case (except by building it into the language)?

For more info about XL, please visit http://xlr.sf.net.


Thanks
Christophe
Formatting is messed up in the above examples...
written by Christophe de de Dinechin, August 28, 2008
It looks like I cannot easily indent. The first example above would be:

function scale(A, B, C : vector) return vector written A*B+C is
...for I in vector.range loop
......result := A*B + C

The dots represent spaces or indent.

Write comment
You must be logged in to a comment. Please register if you do not have an account yet.

busy

Get your FREE Subscription to Dr. Dobb’s Digest today!

Dobbs Code Talk Quick Poll

This time next year, your most important operating system (host and/or target) will be:

Look Who's Code Talking


Robert Jacques
City: Baltimore

Ever Olano
City: American Canyon

Brian Cardarella
City: Boston

Charles Barest
City: Palm Beach Gardens

Michelle Prather
City: Salem

Franck Verrot
City: Lyon

Dobbs Code Talk Tags

.NET abstraction Ada Adobe Agile Ajax algorithm Algorithmic complexity ALM Analogical reasoning Android Anecdotes Apple Application Development AppStore Architecture and Design ARM Artificial Intelligence Artificial Life Assembler Programming Audio files AVX AWK Banking Bazaar Best Practices Blender Books Brain computer interfacing Build C C Programming C Sharp Cartoon Category theory Cellular automata Clojure Cloud Computing Cobol Cocoa Coder Of The Month Cognition as compression Collaboration Common Process/Frameworks Compilers Computational humour Computational narrative Computational politics Computer Science Computers in art computing pioneers concurrency Conferences Consciousness research Contest Contest140 contests CPlusPlus crime CSharp D Programming Data Centers Databases Debugging Delphi Deployment design Design Patterns Digital Signal Processing Distributed Django Documentation DSL dynamic language Eclipse EDA education Emacs Embedded Systems Encryption engineering Erlang Etymology Excel exception handling Facebook Financial computing Five Questions Flash Flash Lite Flex Forth Fortran Fraud FreeBSD Fun Functional Programming gadgets Games Gender Git gnuplot Go Google Graphics GUI hardware Heron High School High-Performance Computing History Holographic reduced representations HTML5 Humanity Humour Hungarian Notation Identity Inkscape Innovation Intel Interview iPhone J2EE Java JavaFX JavaOne JavaScript language engineering Legal lex LINQ Linux Lisp Literate Programming Logic Programming m4 Mainframes Make Mathematica Mercurial Mesh messaging Metaprogramming Microsoft MID Miscellaneous Musings ML Mobile Software Mobility modeling modular programming multicore Music MVC myblog Natural Language Processing Networking Neural networks newspeak Nokia numerical computing Object Rexx ObjectiveC Office Office 2007 Online spreadsheets OOP Open Source Openaccess publishing OpenBSD OpenSolaris Operating Systems Optimization Oracle Pair Programming Parallelism Concurrency Parsing Pascal Patents Patterns Performance Perl PHP Podcast Pop11 Poplog Privacy Processing Productivity Programming Language Implementation Programming Language One Programming language semantics Programming Languages Programming Style Project Management Prolog Psychology Public understanding of science puzzle Python QA Quantum Computing Quotes Rails Realtime recls Requirements Research practice REST Review RIA rich internet applications Robotics Ruby SaaS Software as a service Scala Schadenfreude Science fiction Screencast Scripting SD Best Practices Search Security Semantic Web Silverlight Snobol SOA social Social Networks Society for the Study of Artificial Intelligence a Software Development Methodology and Management Songs and poems Spending Priorities Spreadsheets SQL Startups Statistics Storage String pattern matching Survey Teaching Testing The Business of Programming The Dobbs Challenge The Future Theory Topology Transhumanism Travel on the Job Twitter Types Unix Upgrade Usability Use Cases USENET User Experience User Interface Design Version Control video virtual machines Virtualization Visual Studio Visual Studio Sponsored Post WCF Web Development Windows Windows 7 Windows Live Wireless WOA WPF X Window System yacc

Subscribe to Dr. Dobbs Newsletter

Email:
Dr. Dobb's Update
Delivered twice a week, Dr. Dobb's Update provides unbiased and objective news, commentary and technical features spanning the entire software development marketplace.

Latest Comments

Jonathan's Last Day at Sun
For the 8 years I worked there, it was fantastic. I worked there under McNealy and I have undying admiration for the guy. I only knew Jonathan periphe...
Implementing Thread Local Storage on OS ...
Back in the day, I did a fair amount of work with PThreads. Wonderful design. Some quirks, but basically really, really nice. Although I wrote a lot ...
More Technonecrophilia with Snobol One-L...
Yeah, It's probably identical except for the (embedded) copy number, I would think. Once it became freely distributable, the copy I've been distribut...
More Technonecrophilia with Snobol One-L...
There's a spitbol-3.7-win.exe at http://code.google.com/p/spitbol/downloads/list . I found it via Dave Shield's blog page http://daveshields.wordpress...
Jonathan's Last Day at Sun
Sadness.

The Latest From Our Member Blogs

How To Select Trainees
Written by Joel Wiesen   
01/27/10
Hiring the right trainee can be harder than hiring a trained programmer.  One approach is described at my website: http://www.aprtestingservices.com/business/lpat/
 
Technical Job Interviews
Written by Keith Kerlan   
01/20/10
What is the best way to interview for software developer positions?  I've been on both sides of the job interviewing table, but have been on the interviewee side of some not too  great inter
 
Timers/timeouts in multi-threaded event-loops
Written by Christof Meerwald   
01/03/10
The traditional way to integrate timeout handling (or timers) in (single-threaded) event loops was to just pass the appropriate timeout value to the select/poll/epoll syscall. While this works fine
 
C vs C++
Written by Issam Lahlali   
12/04/09
I think that the debate "C vs C++" will end when the two langages died, and each one have its advantages and inconvenients, the choice of one instead of another depend on the application c
 
Great Jobs at CISCO
Written by Brent Rogers   
11/30/09
Hello! I am a recruiter at CISCO. We have a number of great jobopportunities at CISCO right now. Please take a look at the job links listedbelow and please send me an updated resume if you are interes
 
OK Labs, ST-Ericsson, and the Mobile/Wireless Ecosystem
Written by Steve Subar   
11/17/09
Two weeks ago, OK Labs and ST-Ericsson announced the selection of OK Labs as ST-Ericsson's mobile virtualization partner. To earn this coveted position, OK Labs prevailed in a rigorous evaluation
 
C++ Ninjas Needed in Santa Clara, California
Written by Brent Rogers   
09/30/09
Hello! I am a recruiter at CISCO. Our PostPath teamin Santa Clara is building a new Email SaaS business at CISCO. We are looking forsenior developers with Zimbra expertise to help us accomplish this t
 
Fighting Fragmentation with Mobile Virtualization
Written by Steve Subar   
09/21/09
Last week Motorola and T-Mobile announced the launch of a new and innovative Android-based smartphone, the Cliq. This attractive, feature-rich slider handset happens to build on a chipset and firmware
 
Insights into Router Design: Unit Testing of Networking Protocols
Written by Rajesh Kumar Venkateswaran   
09/07/09
  Unit testing is a software validation methodology through which a programmer tests individual modules or units of source code. If the programmer has been responsible for developing a networ
 
Insights into Router Design: Implementation of Networking Protocols
Written by Rajesh Kumar Venkateswaran   
09/06/09
  Modern data networking consists of a large number of networking protocols, each of which has its own domain of applicability. Some run on end stations (also called hosts), some on enterp
 
Insights and Innovations in Networking
Written by Rajesh Kumar Venkateswaran   
09/05/09
Networking devices such as routers and switches have evolved quite a bit over the past years, both in the service provider network and in the enterprise. It is a challenge to build these devices, bo
 
reddit threads community
Written by Christof Meerwald   
08/30/09
I have just started a threads community over at reddit to cover topics such as multithreading, concurrency and parallel programming. Feel free to join if you are interested. -- cmeerw.org 
 

The Latest From Dr. Dobbs

DDJ